[삼성 기출 문제] 백준 16234 인구 이동

문제 링크

어떻게 풀까?

굉장히 전형적인 bfs 문제입니다.

이 문제를 해결하기 위해서는 크게 세 가지의 생각이 필요합니다.

1. 인구 차이가 L명 이상, R명 미만인 인접한 국가를 묶어서 연합으로 만드는 방법

2. 연합이 된 국가의 인구수를 바꾸는 방법

3. 연합이 되는 국가가 없어서 수행을 종료하는 방법

일단 1, 2방법을 한 번에 묶을 수 있는 방법이 있습니다.

바로 B.F.S입니다.

연합된 국가를 찾으려고 할 때마다, 2차원 배열을 모두 돌면서 인구차이가 L명 이상, R명 이하가 나는 국가를 모두 연합해서 큐에 넣습니다.

그리고 큐에 들어갈때 마다 해당 국가의 인구수를 모두 더합니다. 

이제 마지막에 모든 국가의 인구수와 큐에 들어있는 국가의 수를 나누면 균등하게 나눠진 인구 값이 나옵니다.

이제, 큐에서 국가들을 꺼내면서 해당 국가의 인구수를 균등하게 나눠진 인구 값으로 채워 넣으면 됩니다!

그림으로 과정을 한번 살펴봅시다.

처음 상태는 위 그림과 같습니다.

L = 20, R = 50 입니다.

이제 (1,1)부터 검사를 합니다. (1,1)과 (1,2)와 (2,1)의 인구 차이가 20이기 때문에 두 나라 모두 (1,1)과 연합이 됩니다.

연합 인구는 50+30+30 = 110입니다.

현재 큐의 크기는 3이고, 110 / 3 = 36이기 때문에 큐에서 국가들을 뺀 뒤에 해당 국가의 인구수를 36으로 바꿉니다.

결과는 아래와 같아집니다.

코드는 다음과 같이 나타납니다.

    int map[50][50];
    int N, L, R;
 
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
 
    queue<pair<int, int>> q;      //bfs용
    queue<pair<int, int>> pos; //연합의 좌표를 저장
 
    for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (visited[i][j] == ch) continue;
                int sum = map[i][j];
                q.push({ j, i });
                pos.push({ j, i });
                visited[i][j] = ch;
 
                while (!q.empty()){
                    int x_tmp = q.front().first;
                    int y_tmp = q.front().second;
                    q.pop();
 
                    for (int k = 0; k < 4; k++){
                        int x = x_tmp + dx[k];
                        int y = y_tmp + dy[k];
                        if (x < 0 || y < 0 || x >= N || y >= N || visited[y][x] == ch || ABS(map[y_tmp][x_tmp] - map[y][x]) < L || ABS(map[y_tmp][x_tmp] - map[y][x])>R)
                            continue;
 
                        q.push({ x, y });
                        pos.push({ x, y });
                        sum += map[y][x];
                        visited[y][x] = ch;
                    }
 
                }
 
 
                int avr = sum / pos.size();
 
                while (!pos.empty()){
                    map[pos.front().second][pos.front().first] = avr;
                    pos.pop();
                }
            }
        }
    }

3번의 경우는 연합국이 생겼는지에 대한 bool 값을 이용합니다.

연합국이 생겼다는 것은 큐 안에 어떤 국가가 들어갔다는 것을 의미합니다.

큐에 push되는 값이 있다면, 그 때 bool값을 true로 만듭니다.

만약, 2차원 배열을 순환하는 과정에서 bool 값이 false라면, 연합국이 생기지 않았다는 것입니다. 

이 때, 반복문을 빠져나가서 몇 번이나 인구 이동이 생겼는지 확인하면 됩니다!

1,2,3번을 합치면 다음과 같은 코드가 됩니다!

    int map[50][50];
    int N, L, R;
    bool chk = true;
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    int ans = 0;
    queue<pair<int, int>> q;      //bfs용
    queue<pair<int, int>> pos; //연합의 좌표를 저장
 
    while (chk){
        ++ch;
        chk = false; ans += 1;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (visited[i][j] == ch) continue;
                int sum = map[i][j];
                q.push({ j, i });
                pos.push({ j, i });
                visited[i][j] = ch;
 
                while (!q.empty()){
                    int x_tmp = q.front().first;
                    int y_tmp = q.front().second;
                    q.pop();
 
                    for (int k = 0; k < 4; k++){
                        int x = x_tmp + dx[k];
                        int y = y_tmp + dy[k];
                        if (x < 0 || y < 0 || x >= N || y >= N || visited[y][x] == ch || ABS(map[y_tmp][x_tmp] - map[y][x]) < L || ABS(map[y_tmp][x_tmp] - map[y][x])>R)
                            continue;
                        chk = true;
                        q.push({ x, y });
                        pos.push({ x, y });
                        sum += map[y][x];
                        visited[y][x] = ch;
                    }
 
                }
 
 
                int avr = sum / pos.size();
 
                while (!pos.empty()){
                    map[pos.front().second][pos.front().first] = avr;
                    pos.pop();
                }
            }
        }
 
    }

반복문을 탈출하면 인구 이동이 여태까지 몇 번 일어났는지 출력합시다.

코드

#include <iostream>
#include <queue>
 
#define ABS(x) ((x) > 0 ? (x) : -(x))
using namespace std;
 
int visited[50][50];
int ch;
 
int main(){
    ios_base::sync_with_stdio(false);
    int map[50][50];
    int N, L, R;
    bool chk = true;
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    int ans = 0;
    queue<pair<int, int>> q;      //bfs용
    queue<pair<int, int>> pos; //연합의 좌표를 저장
 
    cin >> N >> L >> R;
 
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++)
            cin >> map[i][j];
    }
 
    while (chk){
        ++ch;
        chk = false; ans += 1;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (visited[i][j] == ch) continue;
                int sum = map[i][j];
                q.push({ j, i });
                pos.push({ j, i });
                visited[i][j] = ch;
 
                while (!q.empty()){
                    int x_tmp = q.front().first;
                    int y_tmp = q.front().second;
                    q.pop();
 
                    for (int k = 0; k < 4; k++){
                        int x = x_tmp + dx[k];
                        int y = y_tmp + dy[k];
                        if (x < 0 || y < 0 || x >= N || y >= N || visited[y][x] == ch || ABS(map[y_tmp][x_tmp] - map[y][x]) < L || ABS(map[y_tmp][x_tmp] - map[y][x])>R)
                            continue;
                        chk = true;
                        q.push({ x, y });
                        pos.push({ x, y });
                        sum += map[y][x];
                        visited[y][x] = ch;
                    }
 
                }
 
 
                int avr = sum / pos.size();
 
                while (!pos.empty()){
                    map[pos.front().second][pos.front().first] = avr;
                    pos.pop();
                }
            }
        }
 
    }
    cout << ans - 1;
}

시간 복잡도

그리고, 인구 이동이 일어날때 마다 배열을 모두 순환합니다.

인구 이동이 k번 일어난다고 한다면, 시간복잡도는 입니다.