백준 16234번 '인구 이동' 파이썬(Python) / 구현, 시뮬레이션, 그래프 탐색(BFS/DFS)

난이도 : 골드4 소요시간 : 70분 문제 태그 #구현 #시뮬레이션 #그래프탐색 #bfs #dfs 나는 bfs로 풀었다. 그래프 탐색 기반 구현 및 시뮬레이션 문제라, 구현 시간이 조금 걸릴 수 있는 문제이다.

문제 설명 문제에서 준 조건 자체는 간단하다. 1) 두 맞닿은 국가에 대해, L이상의 R이하만큼 차이가 난다면 국경이 열린다. 2) 국경이 열리고 서로 맞닿아 있는 국가들끼리는 "연합"이 된다. 3) 모든 연합이 정해졌으면, 각 연합끼리는 인구 수를 1/n씩 나눠 가진다. ----여기까지 하나의 turn 4) 인구 이동이 더 일어나지 않을 때까지 1)~3) 과정을 반복하며, 정답 출력은 총 turn의 개수가 된다.

하지만 5번 예시가 이 문제의 핵심이자, 함정이라 할 수 있다. 한 번의 turn에서, 단순히 한 개의 연합만 존재하지 않는다.

여러 개의 서로 다른 연합이 존재할 수 있다. 5번은 아래와 같이 turn이 2개일 것으로 오해하기 쉽다. 이는 한 turn에서 하나의 ...