[BOJ] 백준 16234. 인구 이동

▶문제설명

[BOJ] 백준 16234. 인구 이동

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

▶Hint

---

DFS, 시뮬레이션 문제이다.

인구 이동이 일어났다는 것은 한 시점에 인구 수 변동이 한 번 이상 있었다는 것을 의미한다.

한 번에 모든 연합이 동시에 인구이동을 실시하기 때문에 순차적으로 인구이동을 시키지 않도록 주의한다.

[입력]

3 5 10
10 15 20
20 30 25
40 22 10

이런 입력이 들어왔다고 했을 때

인구 이동이 한 번 일어난 뒤의 상태는 아래와 같다.

20 20 20

20 20 20

40 20 10

▶Solution

---

DFS 알고리즘을 이용해 각 연합의 전체 인구 수와 연합을 이룬 칸의 개수를 구해서 평균 값을 구한다.

DFS를 수행하면서 좌표 값을 저장해두면 간단히 값을 업데이트 할 수 있다.

DFS를 수행 한 뒤 저장된 좌표의 개수가 2개 이상이면 인구 이동이 일어난 것으로 보고 flag를 true로 설정한다.

flag가 true인 경우 ans 값을 증가시키고, 그렇게 인구 이동이 더이상 일어나지 않을 때까지 반복한다.

[소스 보기]