인구이동

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

2018년 하반기 대졸 신입 삼성 코딩 테스트 오전 타임 2번 탐색 문제이다.

매우 쉬웠다. 55분 소요되었다.

풀이

1. 국경선 열기

   국가 각 지점에서 DFS을 실행하여 각 국가에 지역 번호를 매긴다.

   각 지점에서 동서남북으로 연결되어 있고, 인구 차가 l 이상 r 이하이면 같은 지역 번호가 매겨진다.

   DFS를 실행하고 리턴되었을 때, 지역 번호가 2개 이상 매겨졌으면 연합이 생성된 것이다.

   리스트에 지역번호와 함께 연합의 (인구합 / 연합을 이루는 국가수) 를 저장한다.

2. 인구 이동

   i,j 의 지역번호가 리스트에 저장되어 있는 지역 번호라면 해당 index의 리스트의 인구를 map에 저장한다.

코드

https://github.com/KoJunHee/algorithm/blob/master/src/bj_16234/Main.java