[백준] 17471번 - 게리맨더링 (파이썬) 문제 및 풀이

문제) 백준 - BFS - 게리맨더링

https://www.acmicpc.net/problem/17471

17471번: 게리맨더링

 

삼성 기출스러운 조합+그래프 탐색 문제였습니다. 조합을 사용할 때, 파이썬 itertools에 내장된 combinations만큼 편한 게 없기 때문에 파이썬의 해결했습니다. N개의 구역 중에 1부터 N//2 구역을 뽑은 후 BFS를 통해 인구 수와 방문한 구역 수를 반환합니다. 마찬가지로, 위에서 뽑은 구역을 제외한 나머지 구역에 대해 인구 수와 구역 수를 계산하여 이전에 계산한 구역 수의 합이 N이면 인구수의 최소를 구한다.

 

Python 소스 코드)

 

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2015000~19999/17471_%EA%B2%8C%EB%A6%AC%EB%A7%A8%EB%8D%94%EB%A7%81.py

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions