백번 열번 백번 열번

게리맨더링

• 백준(BOJ) 17471번 게리맨더링

  알고리즘 풀이/백준(Boj) 2019. 12. 15. 01:39

  문제 : https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이: picked 배열과 나머지 temp 배열을 구한 후 BFS를 통해 연결되있는지 확인한다. 둘 다 연결이 된 상태라면 차를 구한다. picked 배열은 1부터 시작해서 23456까지 탐색하게 된다. 코드 ( C++ )

  Read More