[ BOJ - 16234번 ] 인구 이동 (C++)

 

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

 

 국경선이 열리는지 확인하고(인구 차이가 L이상, R 이하), 국경선이 열리는 나라끼리 연합을 생성하여, 연합 별로 인구 이동을 수행하는 과정을 국경선이 더 이상 열리지 않을 때까지 반복해야 한다.

 

따라서,

1. 연합을 구하는 기능
   • 아직 방문하지 않은 모든 위치에서 BFS 수행 -> 인접한 국가들 중, 국경선이 열리는 국가들을 모두 탐색하며 visited 체크 + 방문한 위치와 인구 수 저장해 반환(연합에 속한 국가들의 위치와 인구 수를 반환)
2. 인구 이동 기능
   • 만약 1번에서 반환된 연합의 크기가 1보다 크면 인구 이동 수행 -> (총 인구 수/연합 크기)로 연합에 속한 국가들의 인구 수를 업데이트(연합의 크기가 1인 경우 인구 이동이 일어나지 않은 것)
   • 반복 별로 인구 이동 했는지 체크해 인구 이동이 일어났을 시 날짜를 세주어야 한다.
3. 위 과정을 인구 이동이 일어나지 않을 때까지 반복하는 기능

3가지 기능들을 구현한 후, 구해진 날짜를 출력하여 문제를 해결할 수 있었다.

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

using namespace std;

struct Cord {
    int x; int y;
    int pop;
};

int N, L, R;
vector<vector<int>> country;
int day = 0;

int dirX[4] = {-1, 1, 0, 0};
int dirY[4] = {0, 0, -1, 1};

vector<Cord> bfs(int x, int y, vector<vector<bool>>& visited) {

    queue<Cord> q;
    vector<Cord> cop;

    cop.push_back({x, y, country[x][y]});
    q.push({x, y, country[x][y]});
    visited[x][y] = true;

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

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

            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;

            if(!visited[nx][ny]) {
                int npop = country[nx][ny];
                int dif = abs(pop - npop);
                if(L <= dif && dif <= R) {
                    visited[nx][ny] = true;
                    cop.push_back({nx, ny, npop});
                    q.push({nx, ny, npop});
                }
            }
        }
    }

    return cop;
}

void move(vector<Cord> cop) {
    int total = 0;
    int size = int(cop.size());
    for (int i = 0; i < size; i++) {
        total += cop[i].pop;
    }

    int pop = total/size;

    for (int i = 0; i < size; i++) {
        int x = cop[i].x;
        int y = cop[i].y;
        country[x][y] = pop;
    }
}

void solve() {

    bool moved = true;

    while (moved) {
        moved = false;
        vector<vector<bool>> visited(N, vector<bool>(N));

        for(int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(!visited[i][j]) {
                    vector<Cord> cop = bfs(i, j, visited);

                    if (cop.size() > 1) {
                        moved = true;
                        move(cop);
                    }
                }
            }
        }

        if (moved) {
            day++;
        }

        vector<vector<bool>>().swap(visited);
    }
}

int main() {

    iostream::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> L >> R;
    country.resize(N, vector<int>(N));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> country[i][j];
        }
    }

    solve();

    cout << day << '\n';

    return 0;
}

 

 풀이 방법의 계획과 계획 검증에 충분한 시간 투자하여 구현 할 때 변수나 예외 상황이 발생하지 않았고, 계획한 내용을 모두 잘 구현했나 검증한 뒤 제출하여 한번에 통과할 수 있었다.