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

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

16234번: 인구 이동

 

문제 설명

NxN 크기의 땅이 있고, 1x1개의 칸으로 나누어져 있다. r행 c열에 있는 나라에는 A[r][c] 명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다.

 

1. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 구경선을 오늘 하루 동안 연다.

2. 국경선이 모두 열렸다면, 인구 이동을 시작한다.

3. 국경선이 열린 인접한 칸의 나라의 인구 수는 (연합의 인구 수) / (연합을 이루고 있는 칸의 개수) 가 된다.

4. 모든 국경선을 닫는다.

 

각 나라의 인구 수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구한다.

인구 이동이 발생하는 일수가 2000번보다 작거나 같은 입력만 주어진다.

N, L, R (1 <= N <= 50, 1 <= L <= R <= 100)

해결

bfs를 돌며 인구 이동을 수행해 주어야 한다.

1. bfs로 모든 나라에 방문하며 인접한 나라의 인구 수 차이가 L 이상, R 이하라면 리스트에 추가해 준다.

2.  리스트에 추가된 나라의 인구들을 (연합의 인구 수) / (연합을 이루고 있는 칸의 개수) 로 바꿔 준다.

3. 인구 이동이 없을 때까지 1, 2번을 반복한다.

 

1, 2번이 반복된 개수를 세어 출력해 주면 된다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, l, r;
int board[51][51];
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };

int range_over(int nx, int ny) {
    return nx < 0 || ny < 0 || nx >=n || ny >= n;
}

int bfs(int visited[51][51], int i, int j) {
    vector<pair<int, int>> v;
    queue<pair<int, int>> q;
    q.push({ i, j });
    v.push_back({ i, j });
    visited[i][j] = 1;

    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = dx[dir] + cur.x, ny = dy[dir] + cur.y;
            if (range_over(nx, ny) || visited[nx][ny]) continue;
            int diff = abs(board[cur.x][cur.y] - board[nx][ny]);
            if (!(diff >= l && diff <= r)) continue;
            visited[nx][ny] = 1;
            q.push({ nx, ny });
            v.push_back({ nx, ny });
        }
    }

    if (v.size() == 1) return 0;

    int sum = 0;
    for (int a = 0; a < v.size(); a++) sum += board[v[a].x][v[a].y];
    for (int a = 0; a < v.size(); a++) 
        board[v[a].x][v[a].y] = sum / v.size();

    return 1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> l >> r;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++)
            cin >> board[i][j];

    int ans = 0;
    while (1) {
        int visited[51][51] = { 0 }, ck = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j] == 0) ck += bfs(visited, i, j);
            }
        }
        if (!ck) break;
        ans++;
    }
    cout << ans;
}