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

문제

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

백준 16234

 

문제 내용

N*N 크기의 땅이 있고, 1*1 크기의 나라들로 채워져 있다.

r행 c열에 있는 나라에는 arr[r][c] 명이 살고 있고, 인접한 나라들끼리는 인구 이동이 일어날 수 있다.

국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 공유하는 국경선을 하루 연다.
위의 조건에 의해 열어야 하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. (소수점은 버린다.)
연합을 해체하고, 모든 국경선을 닫는다.

인구 차이 조건에 만족되지 않아 인구 이동이 일어나지 않을 때까지 며칠이 걸리는지를 구하면 된다.

 

문제 풀이

이 문제는 아래 두 과정을 통해 문제를 풀 수 있다.

1. 연합을 만든다. => bfs로 풀이

2. 연합에 속하는 국가들끼리 인구를 재계산한다.

 

1. 연합을 만든다

따로 시작점이 있는 것이 아니기 때문에, 모든 나라에 대해 bfs를 돌려야 한다.

다만, 이미 visited[i][j]가 0이 아닌 곳은 이미 연합에 포함되었다는 소리이므로 제외해도 좋다.

방문했는데 0인 경우는 없다. (자기 자신만 있더라도 그 나라 혼자서 연합인 것이기 때문)

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, 1, -1};

int n, l, r;
int arr[51][51];
int cnt; // 연합 개수

void makeUnion(vector<vector<int>> &visited) {
    cnt = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // visited[i][j]가 0이 아니면 이미 연합에 속해있으므로, bfs를 돌릴 필요가 X
            if (visited[i][j]) {
                continue;
            }

            // visited[i][j]가 0이라는 뜻은, 자신부터 새로운 연합을 만들어야 한다는 의미
            queue<pair<int, int>> q;
            q.push({i, j});
            cnt++;
            visited[i][j] = cnt; // 몇번 연합인지 기록

            while (!q.empty()) {
                auto point = q.front();
                q.pop();

                for (int i = 0; i < 4; i++) {
                    int nr = point.first + dr[i];
                    int nc = point.second + dc[i];

                    if (nr >= 1 && nc >= 1 && nr <= n && nc <= n && visited[nr][nc] == 0) {
                        int diff = abs(arr[nr][nc] - arr[point.first][point.second]);

                        if (diff >= l && diff <= r) {
                            q.push({nr, nc});
                            visited[nr][nc] = visited[point.first][point.second];
                        }
                    }
                }
            }
        }
    }
}

 

2. 연합에 속하는 국가들끼리 인구를 재계산한다.

위에서 각 연합별로 다른 숫자를 visited에 기입했다. (cnt값)

peopleSum 배열을 만들어서, 연합 별로(cnt값을 인덱스로) 몇 명이 포함되어 있고, 몇 개의 나라가 있는지를 저장한다.

그리고 그 저장된 값으로 인구를 재계산하여 arr배열의 값을 바꾸면 된다.

void changePeopleNum(vector<vector<int>> &visited) {
    vector<pair<int, int>> peopleSum(cnt + 1, {0, 0}); // 연합 별 {인구 수, 국가 수}

    // 연합의 인구수 구하기
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            peopleSum[visited[i][j]].first += arr[i][j]; // 해당 연합에 전체 몇명의 인구가 포함되어있는지 체크
            peopleSum[visited[i][j]].second++; // 해당 연합에 포함된 국가 수 체크
        }
    }

    // 각 나라별로 인구수 세팅
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            arr[i][j] = peopleSum[visited[i][j]].first / peopleSum[visited[i][j]].second;
        }
    }
}

 

전체 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, 1, -1};

int n, l, r;
int arr[51][51];
int cnt; // 연합 개수

void makeUnion(vector<vector<int>> &visited) {
    cnt = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // visited[i][j]가 0이 아니면 이미 연합에 속해있으므로, bfs를 돌릴 필요가 X
            if (visited[i][j]) {
                continue;
            }

            // visited[i][j]가 0이라는 뜻은, 자신부터 새로운 연합을 만들어야 한다는 의미
            queue<pair<int, int>> q;
            q.push({i, j});
            cnt++;
            visited[i][j] = cnt; // 몇번 연합인지 기록

            while (!q.empty()) {
                auto point = q.front();
                q.pop();

                for (int i = 0; i < 4; i++) {
                    int nr = point.first + dr[i];
                    int nc = point.second + dc[i];

                    if (nr >= 1 && nc >= 1 && nr <= n && nc <= n && visited[nr][nc] == 0) {
                        int diff = abs(arr[nr][nc] - arr[point.first][point.second]);

                        if (diff >= l && diff <= r) {
                            q.push({nr, nc});
                            visited[nr][nc] = visited[point.first][point.second];
                        }
                    }
                }
            }
        }
    }
}

void changePeopleNum(vector<vector<int>> &visited) {
    vector<pair<int, int>> peopleSum(cnt + 1, {0, 0}); // 연합 별 {인구 수, 국가 수}

    // 연합의 인구수 구하기
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            peopleSum[visited[i][j]].first += arr[i][j]; // 해당 연합에 전체 몇명의 인구가 포함되어있는지 체크
            peopleSum[visited[i][j]].second++; // 해당 연합에 포함된 국가 수 체크
        }
    }

    // 각 나라별로 인구수 세팅
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            arr[i][j] = peopleSum[visited[i][j]].first / peopleSum[visited[i][j]].second;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> l >> r;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }

    int day = 0;
    while (true) {
        vector<vector<int>> visited(n + 1, vector<int>(n + 1, 0)); // visited는 매번 초기화가 필요해서 인자로 넘겨줌
        makeUnion(visited);

        if (cnt == n * n) { // 연합 개수 == 국가 개수 => 서로 연합된 곳이 없음 (종료)
            break;
        }

        changePeopleNum(visited);
        day++;
    }
    cout << day;
}