백준 16234. 인구 이동

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

16234번: 인구 이동

 

[0][0] 국가부터 차례대로 bfs 알고리즘으로 인접한 국가를 탐색한다.

인접한 국가와의 인구 차이가 범위 이내라면 이동하면서 큐에 푸쉬 and 방문 기록 한다.

이렇게 bfs 알고리즘을 한 번 수행하면 탐색 시작한 국가에서 이동가능한 모든 국가들을 알 수 있고, 그 국가들의 집합이 연합이다. 따라서 연합인 국가들에 대하여 인구를 분배해주면 된다. (이동할때 좌표를 저장 한 후에, 이동 가능한 모든 국가가 나온 이후에 분배한다) 

 

이후 아직 방문하지 않은 국가들을 대상으로 bfs 알고리즘을 반복해 수행한다.

만약 모든 국가들에 대하여 bfs 알고리즘을 수행했는데 인구 변경이 한번도 일어나지 않았다면 더이상 인구 이동이 불가능한 것이므로 종료하고, 한 번이라도 인구 변경이 일어났다면 일수를 증가시키고 다시 모든 국가들에 대하여 탐색한다.