[백준] 16234 - 인구 이동

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

간단한 탐색 문제이고 queue를 이용한 dfs로 풀었다.

 

<C++ 코드>

#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <queue>
using namespace std;
 
int country[50][50];
int vis[50][50];
int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, -1, 0, 1};
 
int main(){
    int n, l, r;
    scanf("%d %d %d", &n, &l, &r);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &country[i][j]);
        }
    }
    int re = 0;
    while(true){
        bool move = false;
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(!vis[i][j]){
                    vis[i][j] = true;
                    queue<pair<int, int> > q;
                    vector<pair<int, int> > v;
                    int sum = country[i][j];
                    q.push(make_pair(i, j));
                    v.push_back(make_pair(i, j));
                    while(!q.empty()){
                        int y = q.front().first, x = q.front().second;
                        q.pop();
                        for(int d=0; d<4; d++){
                            int ay = y + dy[d], ax = x + dx[d];
                            if(ay >= 0 && ay < n && ax >= 0 && ax < n && !vis[ay][ax] && abs(country[ay][ax] - country[y][x]) >= l && abs(country[ay][ax] - country[y][x]) <= r){
                                vis[ay][ax] = true;
                                q.push(make_pair(ay, ax));
                                v.push_back(make_pair(ay, ax));
                                sum += country[ay][ax];
                            }
                        }
                    }
                    if(v.size() > 1){
                        int avg = sum / v.size();
                        for(int k=0; k<v.size(); k++){
                            country[v[k].first][v[k].second] = avg;
                        }
                        move = true;
                    }
                }
            }
        }
        if(!move) break;
        else re++;
    }
    printf("%d", re);
    return 0;
}