[BOJ] 16234번 - 인구 이동

백준 16234번 - 인구 이동

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	22597	9112	4992	35.932%

문제

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번 보다 작거나 같은 입력만 주어진다.

출력

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

---

예제 입력 1

2 20 50
50 30
20 40

예제 출력 1

1

초기 상태는 아래와 같다.

L = 20, R = 50 이기 때문에, 모든 나라 사이의 국경선이 열린다. (열린 국경선은 점선으로 표시)

연합은 하나 존재하고, 연합의 인구는 (50 + 30 + 20 + 40) 이다. 연합의 크기가 4이기 때문에, 각 칸의 인구수는 140/4 = 35명이 되어야 한다. 

예제 입력 2

2 40 50
50 30
20 40

예제 출력 2

0

출처

www.acmicpc.net/problem/16234

16234번: 인구 이동

알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 시뮬레이션

접근 방법

전형적인 시뮬레이션 문제였다.

먼저 국경선을 여는 것을 어떤 방식으로 구현하는 가에 따라서 다른데, 4차원 배열 [i][j][k][l] 을 만들어서 (i,j) - (k,l) 사이의 국경선이 존재하면 true 아니면 false 로 구현하는 방식을 생각 할 수도 있겠다.

 

필자는 최대한 간단하게 구현하기 위해서, 동일한 연합끼리는 같은 번호를 가지게 구현하였다. -1 은 아무런 연합에도 속해있지 않는 상태이다.

 

문제에서 주어진대로, 1. (국경선 열기) 2. ( 인구 이동 ) 3. (국경선 닫기) 과정을 반복하면 되는데

국경선을 여는 과정은 특정 좌표 (y,x) 부터 시작하여 DFS를 통해 인접한 모든 Cell들을 검사한 후 차이가 ${L<=x<=R}$일 경우 동일한 League에 합친다.

 

그러면 국경선을 모두 열고 난 후 같은 연합에 속한 나라들은 같은 League_num을 가지게 되는데, 존재하는 모든 연합들을 순회하며 좌표값을 저장한 다음, 연합에 속한 나라의 인구 합 / 연합을 이루는 나라의 개수 값으로 모든 좌표에 값을 주면된다.

 

이 후 국경선을 닫는 과정으로 모든 league들의 값을 -1로 초기화 해주었다.

 

그런데 TLE가 났다..

소스 코드1 ( TLE )

#include <bits/stdc++.h>
using namespace std;
const int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int N, L, R;
int country[51][51];
int league[51][51];

bool visited[51][51] = {false, };
void open_border(int y, int x, int k){
    for(int i=0; i<4; i++){
        int ny = y + dir[i][0];
        int nx = x + dir[i][1];
        if( ny < 0 || nx < 0 || ny >= N || nx >= N || visited[ny][nx] ) continue;
        int diff = abs( country[y][x] - country[ny][nx] );
        if( diff < L || diff > R ) continue;

        visited[ny][nx] = true;
        league[ny][nx] = k;
        open_border(ny,nx,k);
    }
}
bool move_population(int y, int x){
    // (y,x)기준으로 DFS를 수행하여 해당 연합 의 총 인구 수와 연합을 이루는 나라의 개수를 구한다.
    // 연합을 이루는 나라의 개수가 1개일 경우, 의미가 없으므로 false 를 리턴
    int league_num = league[y][x];
    int cnt = 0, sum = 0;

    vector<pair<int,int>> v;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if( league_num == league[i][j] ){
                v.push_back({i,j});
                league[i][j] = -1;
                cnt += 1, sum += country[i][j];
            }
        }
    }

    if( cnt == 1 ) return false;

    int population_per_cell = sum / cnt;
    for( auto it : v ){
        country[it.first][it.second] = population_per_cell;
    }

    return true;
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    int answer = 0;
    while(true){
        memset(visited, false, sizeof(visited));
        memset(league, -1, sizeof(league));
        // 국경선 열기
        int k = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if( !visited[i][j] ){
                    visited[i][j] = true;
                    league[i][j] = k;
                    open_border(i,j,k++);
                }
            }
        }

        // 인구 이동
        // 모든 셀들에 대해 move_population을 수행하였을 때, 모두 false이면 break;
        bool canContinue = false;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if( league[i][j] == -1 ) continue;
                if( move_population(i,j) == true )
                    canContinue = true;
            }
        }
        if( !canContinue ) break;

        answer += 1;
    }
    cout << answer ;
    return 0;
}

무엇이 문제였을까 ? 시간복잡도를 계산해보자.

위의 코드에서 시간 복잡도에 가장 큰 영향을 주는 부분은 move_population 부분이다.

move_population내부에서 $N^2$의 반복을 무조건 수행하는데, 그럴 경우 해당 블록에서 최악의 경우 ${O(N^4)}$의 시간복잡도를 가지게 된다. while문은 최대 2000번이 돌아 갈 수 있으므로, 최악의 경우 2000 * 50^4 인 1.25... * 10^10 의 경우가 나오게 되므로 TLE 를 초래 했던 것 같다.

 

move_population 에서 개선할 수 있는 부분은 2중 for 문을 돌며 모든 나라들을 확인하지 않고 특정 union에 속해있는 것들만 계산을 한 다음 visited처리를 한다면( 여기서 league를 -1로 초기화 해주는 방식으로 진행하였다. ) 불필요한 탐색을 하지 않기 때문에 N*N만큼의 탐색 보다 훨씬 더 적은 시간에 연산이 가능할 것이다.

 

 

소스 코드2 

#include <bits/stdc++.h>
using namespace std;
const int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int N, L, R;
int country[51][51];
int league[51][51];

bool visited[51][51] = {false, };
void open_border(int y, int x, int k){
    for(int i=0; i<4; i++){
        int ny = y + dir[i][0];
        int nx = x + dir[i][1];
        if( ny < 0 || nx < 0 || ny >= N || nx >= N || visited[ny][nx] ) continue;
        int diff = abs( country[y][x] - country[ny][nx] );
        if( diff < L || diff > R ) continue;

        visited[ny][nx] = true;
        league[ny][nx] = k;
        open_border(ny,nx,k);
    }
}
vector<pair<int,int>> v;
int league_num, cnt, sum ;
void DFS(int y, int x, int league_num){
    for(int i=0; i<4; i++){
        int ny = y + dir[i][0];
        int nx = x + dir[i][1];
        if( ny < 0 || nx < 0 || ny >= N || nx >= N ) continue;
        if( league[ny][nx] == -1 ||  league_num != league[ny][nx] ) continue;
        cnt += 1;
        sum += country[ny][nx];
        league[ny][nx] = -1;
        v.push_back({ny,nx});
        // test
        //cout << "cnt : " << cnt << ", sum : " << sum << ", league_num = " << league_num << '\n';
        //
        DFS(ny,nx,league_num);
    }
}
bool move_population(int y, int x){
    // (y,x)기준으로 DFS를 수행하여 해당 연합 의 총 인구 수와 연합을 이루는 나라의 개수를 구한다.
    // 연합을 이루는 나라의 개수가 1개일 경우, 의미가 없으므로 false 를 리턴
    cnt = 1, sum = country[y][x], league_num = league[y][x];
    v.clear();
    if( league_num != -1 ) {
        v.push_back({y,x});
        league[y][x] = -1;
        DFS(y, x, league_num);
    }

    if( cnt == 1 ) return false;

    int population_per_cell = sum / cnt;
    for( auto it : v ){
        country[it.first][it.second] = population_per_cell;
    }

    return true;
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    int answer = 0;
    while(true){
        memset(visited, false, sizeof(visited));
        memset(league, -1, sizeof(league));
        // 국경선 열기
        int k = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if( !visited[i][j] ){
                    visited[i][j] = true;
                    league[i][j] = k;
                    open_border(i,j,k++);
                }
            }
        }

        // 인구 이동
        // 모든 셀들에 대해 move_population을 수행하였을 때, 모두 false이면 break;
        bool canContinue = false;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if( league[i][j] == -1 ) continue;
                if( move_population(i,j) == true )
                    canContinue = true;
            }
        }
        if( !canContinue ) break;

        answer += 1;
    }
    cout << answer ;
    return 0;
}