[C++]백준 16234번 인구 이동

📌문제 링크

---

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

📌문제 설명

---

입력으로 받은 N×N 크기의 인구 배열을 기반으로, 각 칸을 탐색하며 인접 국가 간의 인구 차이가 조건(L ≤ 차이 ≤ R)을 만족하면 국경을 열어 연합을 형성합니다. BFS를 통해 연합에 포함된 칸들의 인구 총합과 개수를 계산한 뒤, 새로운 인구값으로 갱신합니다. 이동이 발생하면 인구 정보를 업데이트하고, 이동이 더 이상 없을 때까지 이를 반복합니다. 최종적으로 인구 이동이 발생한 일수를 출력하며, 효율적인 시뮬레이션을 위해 방문 배열과 새로운 인구 배열을 초기화하며 진행합니다.

📌코드

---

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

bool visited[51][51];
int N, L, R, mp[51][51], answer, newMp[51][51];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void input() {
    cin >> N >> L >> R;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> mp[i][j];
        }
    }
}

void init() {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            visited[i][j] = false;
            newMp[i][j] = mp[i][j];
        }
    }
}

void bfs(int x, int y) {
    vector<pair<int, int>> united;
    queue<pair<int, int>> q;
    
    q.push({x, y});
    united.push_back({x, y});
    visited[x][y] = true;
    
    int total = mp[x][y];
    int count = 1;
    
    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            
            if (nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny]) 
                continue;
            
            int diff = abs(mp[cx][cy] - mp[nx][ny]);
            if (diff >= L && diff <= R) {
                q.push({nx, ny});
                united.push_back({nx, ny});
                visited[nx][ny] = true;
                total += mp[nx][ny];
                count++;
            }
        }
    }
    
    if (count > 1) {
        int newValue = total / count;
        for (auto [ux, uy] : united) {
            newMp[ux][uy] = newValue;
        }
    }
}

void solve() {
    input();
    answer = 0;
    
    while (true) {
        init();
        bool moved = false;
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    bfs(i, j);
                }
            }
        }
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (mp[i][j] != newMp[i][j]) {
                    moved = true;
                }
                mp[i][j] = newMp[i][j];
            }
        }
        
        if (!moved) {
            break;
        }
        answer++;
    }
    
    cout << answer;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}