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

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

16234번: 인구 이동

 

문제 분석

문제에 대한 설명은 안 해도 될 정도로 문제에 자세히 나와있다. 이 문제를 풀기 위해 나는 BFS를 활용해야겠다고 생각했다. 인접 나라 간 국경을 개방하는 조건이 두 인접한 나라의 인구 차가 L 이상 R 이하이면 국경을 개방하는 것이기 때문에, 인구 차가 L 이상 R 이하이면 BFS를 통해 연합할 수 있도록 조건을 걸어주어 인구 차가 조건을 만족하는 모든 나라들을 "연합" 로 설정하고, "연합" 나라들의 인구를 다 더한 후 연합한 나라의 수로 나눠주어 인구를 갱신하되, 이러한 인구 이동이 몇 번 일어나는지를 체크하면 된다.

 

여기서 조금 신경써야 할 것은 두 가지로, "연합"하는 것을 어떻게 저장하고 처리할지이다. 나는 이 두 가지 과정을 분리해서 봤다. 즉, "연합"할 수 있는 나라들을 분류하는 것과 / "연합"한 나라들 간의 인구 이동을 처리하는 것을 나눠 풀었다.

 

코드

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

using namespace std;

int n, l, r;
int arr[50][50];
queue<pair<int, int>> q;
vector<pair<int, int>> v;
bool visited[50][50];
int mr[4] = {1, 0, -1, 0};
int mc[4] = {0, 1, 0, -1};
int result;

void getInput();
void solve();
void printResult();

void bfs();
void movePeople();

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

    getInput();
    solve();
    printResult();

    return 0;
}

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

void solve() {
    bool repeatFlag = true;

    while (repeatFlag) {
        repeatFlag = false;
        while (!q.empty()) {
            q.pop();
        }
        memset(visited, false, sizeof(visited));

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                v.clear();

                if (!visited[i][j]) {
                    q.push({i, j});
                    visited[i][j] = true;
                    bfs();
                }

                if (v.size() >= 2) {
                    movePeople();
                    repeatFlag = true;
                }
            }
        }

        if (repeatFlag) {
            result++;
        }
    }
}

void printResult() {
    cout << result << "\n";
}

void bfs() {
    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        v.push_back(p);

        for (int i = 0; i < 4; i++) {
            int nr = p.first + mr[i];
            int nc = p.second + mc[i];

            if (nr < 0 || nr >= n || nc < 0 || nc >= n) {
                continue;
            }

            int diff = abs(arr[p.first][p.second] - arr[nr][nc]);
            if (diff >= l && diff <= r && !visited[nr][nc]) {
                q.push({nr, nc});
                visited[nr][nc] = true;
            }
        }
    }
}

void movePeople() {
    int sum = 0;
    for (pair<int, int> p : v) {
        sum += arr[p.first][p.second];
    }
    for (pair<int, int> p : v) {
        arr[p.first][p.second] = sum / v.size();
    }
}

 

코드 설명

입력을 받는 부분과 출력을 하는 부분은 크게 뭐 없어서, solve() 메서드 위주로 설명해보도록 하겠다.

 

먼저 repeatFlag라는 변수를 두었다. 이 변수는 인구 이동이 일어났다면, 다음 턴에도 인구 이동을 시도해봐야 하기 때문에 반복문을 제어하는 변수 자격으로 필요하다. 실질적으로 인구 이동이 일어났는지는 while문 안에서 체크하기 때문에, while문에 진입하면 우선 repeatFlag를 false로 꺼둔다. 이외에도, queue를 비우고 visited 배열을 전부 false로 초기화하는 작업을 우선 수행한다.

 

이제 본격적으로 국가들을 탐색하게 되는데, 모든 국가를 출발로 하여 "연합을 형성할 수 있는지" 를 따져볼 것이다. '오늘' 인구 이동 여부를 체크한 적이 없다면(visited[i][j] == false), 일단 현재 국가(i행 j열)를 queue에 집어넣고 visited[i][j]에 true를 할당해 추후 중복해 검토하지 않도록 배제한다. 그리고 i행 j열 국가에 대해, 연합할 수 있는 인접국들이 있는지를 BFS를 통해 체크해볼 것이다. 연합국은 vector에 집어넣게 되는데, 이 vector의 크기가 2 이상이라면 연합이 형성되었음을 의미한다. 그래서 for문을 돌 때마다 vector를 초기화하되, BFS 이후 vector의 크기가 2 이상이라면 인구 이동을 실시하고, repeatFlag를 true로 설정하는 흐름으로 간다. repeatFlag가 true라는 것은 인구 이동이 일어났음을 의미하므로, while문의 끝자락에서 repeatFlag가 true면 result를 1 증가시키도록 했다.

 

BFS를 할 때, queue에 push 하는 조건은 간단하다. 인구 차이가 L 이상 R 이하이고, 이전에 연합한 적이 없는 나라에 대해서만 queue에 push한다. 즉 queue에 push 하는 것은 연합함을 의미하므로, BFS 과정을 돌며 연합한 나라는 자연스레 vector에 삽입되게 된다.

 

또한 앞서 설명한 것처럼 vector의 크기가 2 이상이면 연합이 생겨 인구 이동이 일어남을 의미하므로, 연합국의 인구를 다 더해 연합국의 수로 나눈 값으로 연합국들의 인구를 재할당하게 된다.

 

크게 어려운 건 아니었는데, BFS 과정에서 vector에 같은 좌표를 여러 번 삽입해서 틀렸습니다 를 받고 아예 다시 풀어 통과할 수 있었다. 조심해야겠다. 그냥 아래와 같은 식으로 같은 좌표를 삽입하도록 코드를 짜서 문제였다.

void bfs() {
    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        v.push_back(p); // 여기 중복

        for (int i = 0; i < 4; i++) {
            int nr = p.first + mr[i];
            int nc = p.second + mc[i];

            if (nr < 0 || nr >= n || nc < 0 || nc >= n) {
                continue;
            }

            int diff = abs(arr[p.first][p.second] - arr[nr][nc]);
            if (diff >= l && diff <= r && !visited[nr][nc]) {
                q.push({nr, nc});
                visited[nr][nc] = true;
                v.push_back({nr, nc}); // 여기 중복
            }
        }
    }
}