[백준 16234 C++] 인구 이동

오늘은 BOJ 16234번 인구 이동 문제에 대해 다뤄보도록 하겠습니다.

인구이동 문제 링크 (BOJ 16234번 문제): https://www.acmicpc.net/problem/16234

16234번: 인구 이동

 

문제 설명 

BOJ 16234 인구 이동 문제는 아래 경우를 반복하여 더 이상 인구 이동이 불가능할 때 인구 이동 횟수를 구해주는 문제입니다. 

 - 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다

 - 위의 조건에 의해 열어야 하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.

 - 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.

 - 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버림

 - 연합을 해체하고, 모든 국경선을 닫는다.

 

아래와 같은 입력이 들어왔다고 가정해봅시다. 

4 1 9
96 93 74 30
60 90 65 96
5 27 17 98
10 41 46 20

 

아래와 같은 계산으로 인해, 한 번만에 더 이상의 인구 변화가 일어나지 않게 됩니다. 

(96, 93, 90) -> (96 + 93 + 90) / 3 = 93 

(74, 65) -> 139/2 = 69

(96,98) -> (96 + 98) / 2 = 97

(5, 10) -> (5 + 10) / 2 = 7

(41, 46) -> (41 + 46) / 2 = 43

 

출력) 1 

 

문제 풀이

BOJ 16234 인구 이동 문제의 핵심은 DFS 알고리즘을 사용하여 해당되는 그룹 간에 계산을 진행하는 것입니다. 

 

알고리즘 원리 

1. 더 이상 인구 이동이 발생하지 않을 때까지 반복

2. N X N 을 다 돌며 연합이 가능한 경우를 DFS를 통해 찾아주며 연합이 가능한 경우 주변 좌표를 저장해줍니다.

   (단, 방문한 곳은 더 이상 방문하지 않습니다.) 

3. 연합이 발생했을 경우, DFS를 하면서 저장했던 주변 좌표에 sum(연합 인구수) / num(사람 수) 계산을 진행해줍니다. 

*주의할 점* 

주변 좌표를 저장하기 위해 사용된  Queue, Vector 를 쓸 때 DFS를 실행하기 전에 Clear 해주기

 

이를 코드로 나타내면 아래와 같이 나타낼 수 있습니다.