[BOJ/C++] 백준 16234 - 인구 이동

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

16234번: 인구 이동

문제 설명

구현 태그에 속한 문제이다. 문제를 요약해보자.

1. 매일 각 나라의 인구를 인접한 나라와 비교하면서, L 이상 R 이하의 인구 수의 차이를 가진 나라와 국경선을 모두 열어 연합을 만든다.
2. 이 연합에 속한 나라들의 인구수의 평균만큼 각 나라의 인구를 세팅한다.
3. 1, 2번 과정을 반복하다가 더 이상 국경선을 열 수 있는 나라가 없을 때 인구 이동을 종료한다.

코드 설명

구현 문제이지만 부분적인 문제 해결을 위해 BFS를 활용하였다. 전체적인 해결 과정은 총 세가지이다.

1. 모든 나라 각각의 인접한 나라에 대해서, 차이가 L 이상 R 이하인 나라의 국경선을 연다.
   • 모든 나라를 시작점으로 넣어 BFS로 연합 국가를 구한다. BFS에서 group 배열에 조건에 합당하는 나라를 넣고 있으며, 연합으로 속한 나라와 인접한 나라를 다시 탐색하는 것을 볼 수 있다.
   • 이 때 주의할 점은, 하루만에 연합이 여러 개 생길 수 있다는 것이다. 이를 고려해 두 가지 처리를 해주었다.
     • 모든 연합을 저장하는 이차원 벡터 groups를 선언하였고, group.size()가 1이 아닌 경우, 즉 시작점만 넣어져서 연합이 형성되지 않은 경우를 제외하고 모든 group을 추가하였다.
     • 이전 연합에 속한 나라가 다음 연합을 탐색 시 또 포함되지 않도록 check 배열을 이중 for문 밖에서 초기화해주었으며, (1) 방문하지 않은 나라를 시작점으로 탐색 (2) 네 방향으로 인접한 나라를 탐색 시 방문한 나라를 제외, 이렇게 두 가지 예외 처리에 check 배열을 사용하였다.
   • 연합이 아무것도 없다면, 더 이상 국경선을 열 수 있는 나라가 없는 것이므로 그때의 날짜(ret)을 출력하고 종료한다.
2. 국경선을 열어 생성된 연합들을 토대로, 연합 내의 나라들의 인구수를 갱신한다.
3. 날짜를 1 더한 후 (ret++) 1번으로 돌아가 반복한다.

코드

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <tuple>
#include <cmath>
using namespace std;

int board[51][51];
bool check[51][51];

int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int n, l, r;
bool isOut(int y, int x) {
    return y < 0 || y >= n || x < 0 || x >= n;
}

void bfs(int y, int x, vector<pair<int,int>> &group) {
    group.emplace_back(y, x); 

    queue<pair<int,int>> q; 
    q.push(make_pair(y, x)); 
    check[y][x] = true;
    while (!q.empty()) {
        tie(y, x) = q.front(); q.pop(); 
        for (int direction = 0; direction < 4; direction++) {
            int ny = y + dy[direction], nx = x + dx[direction];
            if (isOut(ny, nx) || check[ny][nx]) continue;
            int gap = abs(board[y][x] - board[ny][nx]); 
            if (gap >= l && gap <= r) {
                q.push(make_pair(ny, nx)); 
                check[ny][nx] = true; 
                group.emplace_back(ny, nx); 
            }
        }
    }
}

int main() {
    cin >> n >> l >> r;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> board[i][j];

    int ret = 0; 
    while (true) {
        vector<vector<pair<int, int>>> groups;
        memset(check, false, sizeof(check));
        for(int y = 0; y < n; y++)
            for (int x = 0; x < n; x++) {
                if (check[y][x]) continue; 
                vector<pair<int, int>> group; // 현재 시작점과 연합한 나라
                bfs(y, x, group); 
                if (group.size() == 1) continue;  
                groups.push_back(group); 
            }
        if (groups.size() == 0) {
            cout << ret << endl;
            break;
        }

        for (auto group : groups) { 
            int sum = 0; 
            for (auto p : group) 
                sum += board[p.first][p.second]; 
            int renew = sum / group.size(); 
            for (auto p : group)
                board[p.first][p.second] = renew; 
        }
        ret++; 
    }
    return 0;
}