[백준 16234번] 인구 이동- java

문제 설명

1. NxN크기의 땅이 있다.

2. 인구 이동은 인접 국가와의 인구 차이가 최소보다 많아야 하고, 최대보다 적어야 한다.

3. 인구 이동은 인접 국가들의 인구의 평균으로 된다.

풀이 과정

 1. BFS와 몇 가지 구현을 통해 해결 가능하다.

 2. 먼저 모든 국가의 인원에 대해 검색을 진행해 준다.

 3. 현재 국가에 대해 인접 국가가 있으면, 그 국가들을 통해 BFS를 진행한다. 추가로, 현재 국가와 인접한 국가들 모두의 정보를 새로운 Queue united에 저장해 준다.

 4. BFS가 완료되면 이 BFS를 시행한 나라 기준으로 모든 인접 국가들이 united에 저장되었을 것이다. 그렇다면 이 united에 연합국이 존재하는 경우 그 국가들에 평균값을 저장시켜 준다.

 

 예를 들어 크기가 4, 최대 인구차이가 20, 최소 인구 차이가 10이라고 하자

10(A)	20(B)	30(C)	100(D)
20(E)	30(F)	100(G)	100(H)
30(I)	100(J)	110(K)	100(L)
120(M)	110(N)	130(O)	100(P)

1.

    A나라 기준으로 bfs시행시 B, E국가는 연합국이 된다. 그렇다면 다시 B, E국가로부터 bfs가 시작된다.

2. 

    B나라 기준으로 C, F국가는 연합국이 된다.

    E나라 기준으로 I, F국가는 연합국이 된다. <- 여기서 F국가는 겹치기 때문에 이를 받지 않도록 해 주면 좋을 것이다.

3. 

    C나라 기준으는 연합국이 없다.

    F나라 기준으로는 B, E국가가 연합국이 된다. <- 여기도 마찬가지로 B, E국가는 이미 연합에 들어있으니 받지 않도록 해준다.

    I나라 기준으로 E국가가 연합국이 된다. <- 이것도 뺴야함.

 

-> 이렇게 되면 for문을 돌렸을 때, a, b, c, e, f, i 국가들은 이미 연합국에 들어있으므로 체크하지 않는다.

D나라는 연합국이 없다

 

1. 

    G나라 기준으로 K나라는 연합국이 된다.

2. 

    K나라 기준으로 G, J, L나라는 연합국이 된다.

.....요렇게 진행하면  한번의 FOR문을 돌렸을 때 모든 연합국이 구해진다.

 

 

그리고 A나라 기준으로 구한 연합국과 G나라 기준으로 구한 연합국은 서로 다르게 구해야 하므로, 이 두 process사이에 인구 이동을 시행해 주면 된다.

코드