[boj] 백준 16234 인구 이동 - BFS

[문제]

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

16234번: 인구 이동

 

[풀이]

BFS 문제. 각 나라를 모두 돌면서 BFS 탐색을 한다.

인접한 나라와의 인구수 차이가 l 과 r 사이인 연합이 가능한 나라에 대해서는 따로 queue를 선언해 넣어주고, 인구수의 합과 연합국의 개수를 카운트하는 변수를 선언해 갱신해준다. 탐색이 끝나 queue가 비면 연합국에 대해 인구수를 갱신해준다. 또한 인구 이동이 일어날 경우, flag를 true로 바꿔줘 인구 이동이 일어났다는 것을 표시해준다. 계속 다음 나라로 좌표를 이동시키면서 위와 같이 BFS 탐색을 진행하고, 모든 탐색이 끝난 후 인구 이동이 일어나지 않았다면 while문을 탈출, 인구 이동이 일어났다면 answer 값을 증가시키고 다시 탐색을 하기 위해 visited 배열을 초기화 해준다. 

 

[코드]

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace::std;
int n, l, r; //l이상 r이하면 국경이 열림. 인구 이동 가능 -> 연합
int A[50][50] = {0, };
bool visited[50][50];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> l >> r;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> A[i][j];
        }
    }
    int answer = 0;

    while(true){
        bool check = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(!visited[i][j]){
                    queue<pair<int, int>> q;
                    queue<pair<int, int>> loc; // 연합국에 포함될 수 있는 나라
                    visited[i][j] = true;
                    q.push({i, j});
                    loc.push({i, j});

                    int sum = 0;
                    int cnt = 0;

                    while(!q.empty()){
                        int y = q.front().first;
                        int x = q.front().second;
                        q.pop();

                        visited[y][x] = true;
                        sum += A[y][x];
                        cnt++;

                        for(int i=0; i<4; i++){
                            int ny = y + dy[i];
                            int nx = x + dx[i];

                            int diff = abs(A[ny][nx] - A[y][x]);

                            if(ny<0 || ny>=n || nx<0 || nx>=n || visited[ny][nx])
                                continue;

                            if(!visited[ny][nx] && diff >= l && diff <= r){
                                q.push({ny, nx});
                                loc.push({ny, nx});
                                visited[ny][nx] = true;
                                check = true;
                            }
                        }
                    }

                    int newPopulation = sum / cnt;
                    while(!loc.empty()){
                        int y = loc.front().first;
                        int x = loc.front().second;
                        loc.pop();

                        A[y][x] = newPopulation; //인구 갱신
                    }
                }
            }
        }
        if(!check){
            break;
        }
        else{
            answer++;
            memset(visited, false, sizeof(visited));
        }
    }

    cout << answer;

}