백준에 이 문제는 따로 알고리즘 분류가 없지만, 나는 BFS로 푼 문제이다.
두 나라의 인구가 이동하는 조건은 다음과 같다.
위에 해당하는 단계들이 1번의 인구이동이다.
여기서 실수할 수 있는 부분이 있다.
나는 문제를 풀 때, 한 개의 연합국에서 인구이동이 끝날 때 1번의 인구이동이라고 카운트를 세었지만, 정답은 주어진 맵에서 가능한 모든 연합국들의 인구이동이 끝나는 것이 1번의 인구이동이었다.
따라서 문제를 해결하기 위한 로직은 다음과 같다.
1. 주어진 맵의 각 위치마다 BFS를 진행한다. 이 때, 한 번의 인구이동동안 연합국에 해당하는지 확인하기 위한 집합 변수(unions)를 둔다. (11번째 줄)
2. 연합국이 아닌 모든 나라들에 대해서 BFS를 진행한다. (12~33번째 줄)
3. 한 번의 BFS가 끝났을 때, 연합을 이루는 나라가 있다면 인구이동을 하고, 연합국 집합에 추가한다. (34~40번째 줄)
4. 인구이동이 일어났다면 카운트를 센다. (41~44번째 줄)
여담이지만, 파이썬과 같은 집합자료형이 없는 언어라면 disjoin-set(서로소 집합)을 써야할 것 같다.
