[BaekJoon] 백준 17471번 게리맨더링

[BaekJoon] 백준 17471번 게리맨더링 🎈문제 https://www.acmicpc.net/problem/17471 💬설명 2 ≤ N ≤ 10 , 1 ≤ 구역의 인구 수 ≤ 100 제한사항이 위와 같아 0.5초에도 충분이 돌릴 수 있는 양이라고 생각했기 때문에 조합 -> bfs를 이용해 풀어줬다. 문제 풀이 순서 1-N/2만큼의 조합을 구한다. (ex. N=4일때, 길이 1 + 길이 3, 길이 2 + 길이 2의 조합) 구한 조합을 가지고 각각에 대해, 총 2번 bfs를 돌린다. bfs를 돌았을 때 모든 노드가 2개의 선거구로 나뉠 수 있다면(연결되어 있다면) 인구수 차이의 최소값을 update한다. 👩‍💻코드 # BaekJoon17471.py from collections import deque ..