[백준][16234] 인구 이동

이 포스트는 백준 사이트의 인구 이동 문제 풀이입니다.

문제

해결 과정

이 문제는 지도의 원본과 새로운 지도를 나눠 탐색을 해야하는 문제입니다.

문제에서 설명한 인구 이동은 1일 동안 이뤄지며, 더 이상 인구 이동이 없을 때 까지 반복됩니다.
하루동안 이뤄지는 과정은 아래와 같습니다.

1. 국경을 공유(동서남북으로 접한 국가)하는 두 나라의 인구 차이가 \(L <= (인구차이) <= R\) 이면 국경 개방
2. 모든 국경이 열리면 인구 이동 시작
3. 국경이 열린 국가들은 연합으로 묶음
4. 연합의 모든 국가는 \((연합 총 인구수) \div (연합된 나라 수)\) 의 몫으로 인구가 재분배
5. 모든 국경 폐쇄
   
   

1번부터 5번까지 순서를 반복하고
만약, 1번에서 국경이 개방된 곳이 없다면 반복을 종료합니다.

코드 구현

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

struct COUNTRY{
    int row, col, population;
};

vector<vector<int>> board;

void input(int& N, int& L, int& R);
int search_population_count(
    const int N, const int L, const int R, 
    vector<vector<int>>& new_country, COUNTRY start_country,
    vector<vector<bool>>& visited);

int main() {
    int N, L, R;
    input(N, L, R);

    vector<vector<bool>> visited;
    int day = 0;
    while(true) {
        int open_border_cnt = 0;
        visited.assign(N, vector<bool>(N, false));
        auto new_country = board;
        
        for(int row = 0; row < N; ++row) {
            for(int col = 0; col < N; ++col) {
                if(false == visited[row][col]) {
                   open_border_cnt += search_population_count(
                    N, L, R, new_country, {row, col, board[row][col]}, visited
                    );
                }
            }
        }
        if(0 == open_border_cnt) break;
        else day += 1;
        board = new_country;
    }
    cout << day;
    return 0;
}

void input(int& N, int& L, int& R) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> L >> R;
    board.assign(N, vector<int>(N, 0));
    for(int row = 0; row < N; ++row) {
        for(int col = 0; col < N; ++col) {
            cin >> board[row][col];
        }
    }
}

int search_population_count(
    const int N, const int L, const int R, 
    vector<vector<int>>& new_country, COUNTRY start_country,
    vector<vector<bool>>& visited)  
{
    queue<COUNTRY> q;
    q.push(start_country);

    visited[start_country.row][start_country.col] = true;

    int dir_row[4]{-1, 1, 0, 0};
    int dir_col[4]{0, 0, -1, 1};

    int union_population = start_country.population;
    int country_cnt = 1;

    vector<COUNTRY> union_list{ start_country };

    while(false == q.empty()) {
        auto curr = q.front();
        q.pop();

        for(int dir = 0; dir < 4; ++dir) {
            int new_row = curr.row + dir_row[dir];
            int new_col = curr.col + dir_col[dir];

            if(new_row < 0 || new_row >= N || new_col < 0 || new_col >= N)
                continue;
            if(visited[new_row][new_col])
                continue;

            int population_gap = abs(board[curr.row][curr.col] - board[new_row][new_col]);
            if(L <= population_gap && population_gap <= R) {
                visited[new_row][new_col] = true;
                country_cnt += 1;
                union_population += board[new_row][new_col];
                union_list.push_back({new_row, new_col, board[new_row][new_col]});
                q.push({new_row, new_col, board[new_row][new_col]});
            }
        }
    }

    if(country_cnt == 1) {
        return 0;
    }

    int union_avg = (union_population / country_cnt);
    for(auto country : union_list) {
        new_country[country.row][country.col] = union_avg;
    }
    return country_cnt;
}

실행 결과