A. 문제설명
https://www.acmicpc.net/problem/16234
문제에 대한 자세한 설명은 링크 참조
1. N * N 배열 크기의 각 국가에 국민들 수가 주어짐
2. 각 인접한 칸의 국민 수의 차가 L이상 R이하일 때, 두 나라의 국경선을 염
3. 위 조건에 의해 국경을 열어 연합이 인구이동을 하게 될 때, 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다.
4. 각 국가는 인구이동을 가능한 한 최대한 진행한다.
5. 이때 최대로 이루어질 수 있는 인구이동의 횟수를 반환
B. 접근법
시뮬레이션 문제. 문제상의 조건으로 2000 이상의 이동이 이루어지지 않는 입력만 들어온다고 했으므로, 문제의 내용을 충실하게 구현하여 그대로 적용할 수 있는 풀이를 만들어보자.
C. 풀이
1. 각 인접국가별 개방가능 여부를 확인
open_pop() 함수 사용: L <= |인구차이| <= R 를 확인하여 각 인접 칸들의 국경 개방여부를 확인
2. 개방가능 국가 없으면 종료, 있으면 개방 후 인구이동
move_pop()은 DFS 이용하여 인접한 국가들 중 연합을 만들고, 배분한 지점은 마킹, 안한 지점들을 마저 찾아가도록
divide_pop() 함수 사용: sum(연합의 인구) / 연합 수 반환하는 함수
3. 마지막까지 이동 후 이동 횟수 반환
D. 내 코드
