[BOJ 16234] 인구 이동

# 문제

https://www.acmicpc.net/problem/16234

# 풀이

dfs를 사용하여 문제를 풀었습니다.(bfs로 하셔도 괜찮습니다.)

총 3개의 2차원 배열을 사용했습니다. 

일단, 첫 번째는 초기 국가들의 인구수를 2차원 배열입니다.

이 배열을 기반으로 국가간 연합이 가능한지 여부를 매번 따질 수 있게끔 하는 배열입니다.

두 번째는 dfs를 통하여 연합된 국가들을 표시하는 역할을 하는 배열입니다.

나중에 인구수를 재배치 할때, 해당 배열을 보며 인구 수를 분배합니다.

세 번째는 dfs를 할때 가장 중요한 visit 배열입니다. 

탐색을 배우신 분들이라면 이것이 얼마나 중요한지 아실겁니다. :)

이 문제는 단지번호붙이기 라는 문제에서 약간 심화된 문제라고 생각되어 링크를 걸어 놓았습니다.

혹시나 아직 이 문제 어려우신 분들이 있다면 위에 문제를 먼저 풀어보시길 권합니다! 

dfs를 통해 해당 위치에 있는 국가와 밀접한 4개의 국가와 차이가 L에서 부터 R 사이라면 방문하는 식으로 하여 문제를 풀어갑니다.

이때 계속해서 연합국으로 인정된 국가들의 수를 늘려가고, 사람수도 더해갑니다.

이유는 당연히 나중에 해당 연합국의 인구의 평균을 구하기 위해서 이겠죠?

그 이후에 연합국이 나올때 마다 map에다가 해당 연합국의 번호를 key로, 연합국의 (평균 값을 낸)인구수를 value로 하여 넣어줍니다.

나중에 인구수를 재배치 할때, 해당 연합국 번호를 가지고 있다면 (평균 값을 낸)인구수를 넣어주면 쉽게 값을 얻어낼 수 있기 때문에 map을 사용했습니다.

N*N개의 배열을 만들어 사용해도 무방합니다.

여기서 중요한점은 끝나는 조건은 연합국이 없을 때!

즉, 모든 국가가 연합을 할 수있는 조건을 가지지 않고 각각의 국가로써 남아있을 때 끝이 나게 된다고 문제에서 주어져 있습니다.

따라서, 연합국 수 (=연합국 번호)가 N*N이라면 모든 국가가 국경선을 열지 않은 것이기때문에 끝나게 됩니다.

그것이 아니라면, 인구수를 재배치 해줍니다.

이를 while문을 통해 계속해서 돌려주다 종료 조건에 만나면 break를 시켜주는 식으로 돌려주시면 됩니다.

주의 할 점은 visit 배열과, 연합국에 들어간 국가의 수와 인구들은 while문을 돌릴 때마다 초기화를 시켜주셔야 합니다.

# 코드

#include <iostream>
#include <cmath>
#include <map>
#include <cstring>
using namespace std;
 
int N,L,R;
int nation[51][51];
int unionNation[51][51];
bool visit[51][51];
 
int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
 
int nationCnt = 0;
int peopleCnt = 0;
 
void dfs(int r, int c, int n){
    unionNation[r][c] = n;
    visit[r][c] = true;
    peopleCnt += nation[r][c];
    nationCnt++;
    for(int i = 0; i < 4; i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        if(nr < 1 || nr > N || nc < 1 || nc > N) continue;
        if(visit[nr][nc]) continue;
        int diff = abs(nation[r][c] - nation[nr][nc]);
        if(diff >= L && diff <= R){
            dfs(nr,nc,n);
        }
    }
}
 
int main(){
    cin >> N >> L >> R;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cin >> nation[i][j];
        }
    }
    int time = 0;
    while(true){
        memset(visit,false,sizeof(visit));
        int UnionCnt = 0;
        map<int, int> movingPeople;
        //연합국 수와 해당 연합국 인구수 계산
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                if(visit[i][j]) continue;
                peopleCnt = 0;
                nationCnt = 0;
                dfs(i,j,UnionCnt);
                movingPeople[UnionCnt] = peopleCnt/nationCnt;
                UnionCnt++;
            }
        }
        //모든 국가가 연합을 이루지 않을때 종료
        if(UnionCnt == N*N) break;
        //인구수 이동
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                nation[i][j] = movingPeople[unionNation[i][j]];
            }
        }
        time++;
    }
    cout << time << endl;
    return 0;
}