17471
-
[백준]17417: 게리맨더링 - JAVA문제풀이/백준 2021. 5. 26. 12:59
[백준]17417: 게리맨더링 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 구현능력 + 완전탐색 + DFS/BFS 개념을 모두 활용해 볼 수 있는 문제이다. 우선, 문제의 조건을 구현 순서에 맞게 정리해보자. 지역에 두 개의 선거구 중에 하나를 할당한다. (1 또는 2로 표현) 나눠진 지역들이 두개의 구역으로 연결되는지 확인한다. (DFS/BFS 탐색으로 구함) 두 지역의 차이 값 중에서 최소값을 찾아준다. 하나하나씩 살펴보쟝. 1. 지역에 두 개의 선거구..