인구 이동 (feat. 백준, 16234번)

인구 이동
https://www.acmicpc.net/problem/16234

16234번: 인구 이동

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int N, L, R, dx[4], dy[4], arr[50][50];
bool visit[50][50];
bool check(){
    for(register int x = 0, y, d, nx, ny; x < N; ++x)
        for(y = 0; y < N; ++y)
            for(d = 0; d < 4; ++d){
                nx = x + dx[d], ny = y + dy[d];
                if(0 <= nx && nx < N && 0 <= ny && ny < N){
                    register int t = abs(arr[x][y] - arr[nx][ny]);
                    if(L <= t && t <= R)
                        return true;
                }
            }
    return false;
}
void bfs(){
    memset(visit, false, sizeof(visit));
    queue<pair<int, int>> q, node;
    for(register int i = 0, j; i < N; ++i)
        for(j = 0; j < N; ++j)
            if(!visit[i][j]){
                q.push(make_pair(i, j));
                node.push(make_pair(i, j));
                visit[i][j] = true;
                register int sum = arr[i][j];
                while(!q.empty()){
                    auto p = q.front(); q.pop();
                    register int x = p.first, y = p.second;
                    for(register int d = 0, nx, ny; d < 4; ++d){
                        nx = x + dx[d], ny = y + dy[d];
                        if(0 <= nx && nx < N && 0 <= ny && ny < N && !visit[nx][ny]){
                            register int t = abs(arr[x][y] - arr[nx][ny]);
                            if(L <= t && t <= R)
                                visit[nx][ny] = true, q.push(make_pair(nx, ny)), node.push(make_pair(nx, ny)), sum += arr[nx][ny];
                        }
                    }
                }
                sum /= node.size();
                while(!node.empty()){
                    auto p = node.front(); node.pop();
                    arr[p.first][p.second] = sum;
                }
            }
}
int main(){
    ios::sync_with_stdio(false), cin.tie();
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    cin >> N >> L >> R;
    for(register int i = 0, j; i < N; ++i)
        for(j = 0; j < N; ++j)
            cin >> arr[i][j];
    register int days = 0;
    while(1){
        if(!check())
            break;
        bfs();
        ++days;
    }
    cout << days;
    return 0;
}
// *&)*@*

 

1. N * N 전체를 확인하며 이동할 땅이 존재하는지 확인합니다. 만약 없다면 종료시킵니다.
2. 이동할 땅이 존재하는 경우, N * N 전체를 확인하며 bfs로 이어지는 땅들을 찾습니다. 그리고 땅들을 찾았다면 평균값을 해당 땅들에 적용시켜 줍니다. 물론 bfs로 이어진 땅은 flag를 두어 재방문하지 않도록 합니다.
3. 1번의 종료조건이 될때까지 수행하며 2번이 수행된 총 횟수 (날짜) 를 출력하면 됩니다.