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

www.acmicpc.net/problem/16234

16234번: 인구 이동

bfs문제였습니다.

 

풀이방법

 1. 각 국가당 인구를 입력받습니다

 

 2. 이동 할 인구가 없을 때까지 다음을 수행합니다.

 

    2-1. 국경을 열어 연합을 형성했을 때의 인구 지도를 만듭니다. bfs를 통해 인접국가의 차이가 l이상 r이하일 때 같은 연합입니다. 이때 서로 다른 연합의 국가 또한 인접해 있을 수 있습니다. 이 경우 인접은 했으나 차이가 조건에 부합하지 않기 때문에 다른 연합이라고 표시합니다.

 

    2-2. 만든 인구 지도에 형성될 연합이 없다면 break합니다.

 

    2-3. 아니라면 인구 지도를 통해 인구를 이동시킵니다. 각 연합의 크기와 연합 전체 인구를 bfs로 구합니다. 이 때 인구의 좌표(i,j)를 넣어줄 자료구조를 queue로 선언해 확인한 국가의 좌표를 넣어줍니다. 그 후 bfs를 마쳤을 때 나온 연합의 크기, 연합 전체 인구가 구해집니다. queue에는 갱신할 국가의 좌표들이 함께 들어가 있으므로 연합크기 / 연합 전체 인구로 갱신해줍니다.

 

    2-4. 인구이동의 발생 수는 각 연합마다 발생한 인구이동의 횟수가 아닙니다. 인구이동은 하루단위로써 오늘 일어났는지 안 일어났는지만 확인합니다. 따라서 2-3이 일어난 횟수를 구해주는 것이 답입니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int n,l,r,cnt;
int population[51][51];
int checkOpen[51][51];
int visited[51][51];
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
bool haveToMove(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(checkOpen[i][j]) return true;
        }
    }
    return false;
}

void movePopulation(int i,int j){
    queue <pii> q;
    queue <pii> moveQ;
    int area = 1;
    int areaNum = checkOpen[i][j];
    int totalPopulation = population[i][j];
    visited[i][j] = 1;
    q.push({i,j});
    moveQ.push({i,j});
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= n || 0 > ny || ny >= n) continue;
            if(checkOpen[nx][ny] != areaNum || !checkOpen[nx][ny] || visited[nx][ny]) continue;
            visited[nx][ny] = 1;
            area++;
            totalPopulation += population[nx][ny];
            q.push({nx,ny});
            moveQ.push({nx,ny});
        }
    }

    int afterMovedPeopleNum = totalPopulation / area;
    while(!moveQ.empty()){
        int x = moveQ.front().first;
        int y = moveQ.front().second;
        moveQ.pop();
        population[x][y] = afterMovedPeopleNum;
    }
}

void stepOne(){
    queue <pii> q;
    int areaNum = 0;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(visited[i][j]) continue;
            areaNum++;
            visited[i][j] = 1;
            q.push({i,j});
            while(!q.empty()){
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                for(int k = 0; k < 4; k++){
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    if(0 > nx || nx >= n || 0 > ny || ny >= n) continue;
                    if(visited[nx][ny]) continue;
                    int diff = abs(population[x][y] - population[nx][ny]);
                    if(l > diff || diff > r) continue;
                    visited[nx][ny] = 1;
                    checkOpen[x][y] = checkOpen[nx][ny] = areaNum;
                    q.push({nx,ny});
                }
            }
        }
    }
}

void stepTwo(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(!checkOpen[i][j] || visited[i][j]) continue;
            movePopulation(i,j);
        }
    }
}

int main(){
    cin >> n >> l >> r;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> population[i][j];
        }
    }

    while(1){
        memset(checkOpen,0,sizeof(checkOpen));
        memset(visited,0,sizeof(visited));
        stepOne(); //열 국경 check하기
        memset(visited,0,sizeof(visited));
        if(!haveToMove()) break;
        stepTwo(); //연합 국경 인구 이동.
        cnt++;
    }
    cout << cnt << '\n';
}

 

Test Case

 몇 가지 반례들 입니다. 질문게시판을 참고했습니다.

 

input

5 1 5
88 27 34 84 9
40 91 11 30 81
2 88 65 26 75
75 66 16 14 28
89 10 5 30 75

답

1

 

input

4 1 9
96 93 74 30
60 90 65 96
5 27 17 98
10 41 46 20

답

1

 

input

3 10 30
0 0 0  
50 30 0
20 0 40

답

2