백준 16234번 인구이동 (C++)

문제 링크 : www.acmicpc.net/problem/16234

16234번: 인구 이동

 

이 문제는 유의 사항이 하나 있다.

 

<문제 설명 중 발췌>

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

예를 들어 하루 동안 위와 같은 인구이동 구역이 발생한다고 가정하자.

하늘색 지역은 하늘색 지역끼리, 보라색 지역은 보라색 지역끼리 인구이동이 이루어진다.

이는 모두 하루만에 이루어지며, 고로 총 인구이동 횟수는 2번이 아닌 1번이다.

 

때문에 관건은 하루안에 인구이동이 가능한 지역들을 구분하여 인구이동을 발생시키는 것이다.

 

문제 풀이는 다음과 같다.

1. 배열의 모든 위치를 판단할 pair<int,int>형 큐 1개, 동시에 인구이동이 가능한 지역끼리 인구이동을 진행할 pair<int,int>형 큐1개. 총 2개의 큐를 만든다.

2. 아래는 이 문제의 핵심인 BFS코드이다. 먼저 크게 윤곽을 보고 다음 설명부터 세세하게 이해해보자.

    while(true){
        done = false;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(ch[i][j]) continue;
                q.push({i,j});
                q2.push({i,j});
                ch[i][j] = true;
                people = arr[i][j];
                country = 1;
                while(!q.empty()){
                    y = q.front().first;
                    x = q.front().second;
                    for(int i=0; i<4; i++){
                        ny = y + my[i];
                        nx = x + mx[i];
                        if(ny>=1&&ny<=n&&nx>=1&&nx<=n&&!ch[ny][nx]&&abs(arr[y][x]-arr[ny][nx])>=l&&abs(arr[y][x]-arr[ny][nx])<=r){
                            ch[ny][nx] = true;
                            q.push({ny,nx});
                            q2.push({ny,nx});
                            done = true;
                            people += arr[ny][nx];
                            country++;
                        }
                    }
                    q.pop();
                }
                while(!q2.empty()){
                    y = q2.front().first;
                    x = q2.front().second;
                    arr[y][x] = people / country;
                    q2.pop();
                }
            }
        }
        memset(ch,false,sizeof(ch));
        if(done) ans++;
        else break;
    }

3. 첫 번째 단락은 아래와 같다.

    while(true){
        done = false;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(ch[i][j]) continue;
                q.push({i,j});
                q2.push({i,j});
                ch[i][j] = true;
                people = arr[i][j];
                country = 1;

보다시피 while문안에 이중 for문이 구성되어있다. 이는 인구이동이 일어난 후, 변화된 값을 통해 다음날부터 또 다른 인구이동이 일어날 수 있기 때문에 구성된 구조이다. done이라는 함수는 인구이동이 전혀 일어나지 않아 while문을 나가야 할 때 판단하는 조건으로 사용되었다.

2중 for문을 보면 먼저 해당 지역을 방문한 적이 있으면 continue를 진행한다. 그렇지 않을 경우, 큐1와 큐2에 해당 위치를 넣어준다.

이때 people은 누적되는 사람의 수이며, country는 인구이동이 일어나는 국가의 갯수이다.

 

4. for문 안에 위치한 while문 2개이다.

                while(!q.empty()){
                    y = q.front().first;
                    x = q.front().second;
                    for(int i=0; i<4; i++){
                        ny = y + my[i];
                        nx = x + mx[i];
                        if(ny>=1&&ny<=n&&nx>=1&&nx<=n&&!ch[ny][nx]&&abs(arr[y][x]-arr[ny][nx])>=l&&abs(arr[y][x]-arr[ny][nx])<=r){
                            ch[ny][nx] = true;
                            q.push({ny,nx});
                            q2.push({ny,nx});
                            done = true;
                            people += arr[ny][nx];
                            country++;
                        }
                    }
                    q.pop();
                }
                while(!q2.empty()){
                    y = q2.front().first;
                    x = q2.front().second;
                    arr[y][x] = people / country;
                    q2.pop();
                }
            }
        }

q에는 인구이동이 가능한 지역들끼리 저장해준다. 인구이동이 가능한 지역들끼리 모두 저장해서 더 이상 저장 가능한 지역이 없을 경우, q2에 대한 while문이 진행된다. q2는 저장된 지역들에 평균 인구값을 저장하는 과정이다.

 

5. 이 부분은 2중 for문을 모두 마치고 바로 뒤에오는 코드이다.

        memset(ch,false,sizeof(ch));
        if(done) ans++;
        else break;

방문했던 지역들을 모두 false로 바꾸어준다. 만약 한 번이라도 인구이동이 일어났다면 ans 값을 +1 해준다. 그렇지 않을 경우 더 이상의 인구 이동은 일어날 수 없다는 뜻이므로, while문을 종료해준다.

 

6. 답을 출력한다.

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int arr[51][51], my[] = {-1,0,1,0}, mx[] = {0,-1,0,1}, y, x, ny, nx, n, l, r, ans = 0, people = 0, country = 0;
bool ch[51][51], done;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> l >> r;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++) cin >> arr[i][j];
    }
    queue<pair<int,int>> q;
    queue<pair<int,int>> q2;
    while(true){
        done = false;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(ch[i][j]) continue;
                q.push({i,j});
                q2.push({i,j});
                ch[i][j] = true;
                people = arr[i][j];
                country = 1;
                while(!q.empty()){
                    y = q.front().first;
                    x = q.front().second;
                    for(int i=0; i<4; i++){
                        ny = y + my[i];
                        nx = x + mx[i];
                        if(ny>=1&&ny<=n&&nx>=1&&nx<=n&&!ch[ny][nx]&&abs(arr[y][x]-arr[ny][nx])>=l&&abs(arr[y][x]-arr[ny][nx])<=r){
                            ch[ny][nx] = true;
                            q.push({ny,nx});
                            q2.push({ny,nx});
                            done = true;
                            people += arr[ny][nx];
                            country++;
                        }
                    }
                    q.pop();
                }
                if(q2.size()!=1){
                    while(!q2.empty()){
                        y = q2.front().first;
                        x = q2.front().second;
                        arr[y][x] = people / country;
                        q2.pop();
                    }
                }
                else q2.pop();
            }
        }
        memset(ch,false,sizeof(ch));
        if(done) ans++;
        else break;
    }
    cout << ans << "\n";
    return 0;
}

시간을 조금이라도 단축해보고자 q2부분에 약간의 변형을 가했다.

사이즈가 1인 경우엔 인구 이동이 필요없으므로 스킵하는 구조로 변경했다.

 

문제 자체는 무난한 난이도였는데, 처음에 해석을 잘못해서 틀리고 말았다.