BaekJoon
[BaekJoon] 17471번 게리맨더링 (Java) 문제 풀이 [Gold 3]
문제https://www.acmicpc.net/problem/17471 어떻게 풀 것인가?문제의 접근조차 어려워서 잠깐의 고민 끝에 결국엔 다른분의 풀이를 참고하였다. 오늘의 포스팅은 기억을 남기기 위한 용도라고 생각하며 작성하였다. 문제의 접근의 경우 지역에 두 개의 선거구 중에 하나를 할당한다. (1 또는 2로 표현)나눠진 지역들이 두개의 구역으로 연결되는지 확인한다. (DFS/BFS 탐색으로 구함)두 지역의 차이 값 중에서 최소값을 찾아준다.좀 더 풀어서 작성해보자. 먼저, 입력을 통해 각 지역의 인구 수와 연결된 지역 정보를 받아 저장한다. 이후, 선거구를 나누기 위해 각 지역이 속할 선거구를 정하는 모든 경우의 수를 탐색한다. 이를 위해 깊이 우선 탐색(DFS)을 사용하며, 각 지역을 두 개의 ..
