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

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

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

출력

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

코드

#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>
using namespace std;
 
struct q_city{
    int x;
    int y;
    int val;
};
 
int N, L, R;
int sum, city, ans;
int map[51][51];
queue<q_city> q;
queue<q_city> uni_v;
bool visited[51][51];
bool is_uni;
int p_x[4] = { 1,0,-1,0 };
int p_y[4] = { 0,-1,0,1 };
q_city info;
 
 
void make_uni() {
 
    while (!q.empty()) {
        int cur_val = q.front().val;
        int cur_x = q.front().x;
        int cur_y = q.front().y;
        sum += cur_val; city++;
        q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur_x + p_x[dir];
            int ny = cur_y + p_y[dir];
            int cpm_val = abs(cur_val - map[ny][nx]);
            if (nx > 0 && nx < N + 1 && ny > 0 && ny < N + 1 && !visited[ny][nx]) { //범위 안이고 방문하지 않았을경우
                if (cpm_val >= L && cpm_val <= R) {   // 도시의 인구차가 L명이상 R명 이하면
                    is_uni = true;
                    visited[ny][nx] = true;
                    info.x = nx; info.y = ny; info.val = map[ny][nx];
                    uni_v.push(info);
                    q.push(info);
                } //L<x<R
            } //범위안 방문 x
        } //for 4방향
    }//while
    int insert_ans = sum / city;
    while (!uni_v.empty()) {
        map[uni_v.front().y][uni_v.front().x] = insert_ans;
        uni_v.pop();
    }
    
}
 
void move_h(int move_cnt) {
    is_uni = true;
    while (is_uni) {
        is_uni = false;
        ans = move_cnt;
        move_cnt++;
        for (int Y = 1; Y <= N; Y++) {
            for (int X = 1; X <= N; X++) {
                if (visited[Y][X]) continue;
                sum = 0; city = 0;
                visited[Y][X] = true;
                info.val = map[Y][X]; info.x = X; info.y = Y;
                uni_v.push(info);
                q.push(info);
                make_uni();
            }
        }
        memset(visited, false, sizeof(visited));
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> N >> L >> R;
    for (int Y = 1; Y <= N; Y++) {
        for (int X = 1; X <= N; X++) {
            cin >> map[Y][X];
        }
    }
    move_h(0);
    cout << ans;
}

해설

bfs를 통해 풀이를 했습니다.