백준 17471. 게리맨더링

최근 코딩테스트 준비겸, 삼성 A형 기출문제들을 풀고 있는데, 삼성 기출문제는 대부분 비슷한 유형의 완전탐색이다.

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

17471번: 게리맨더링

 Branch & Bound 기법을 이용하여 풀었다. 답은 될 수 없지만 초기 답을 한 선거구에만 사람이 몰렸을 때를 기준으로

설정하고, 선거구를 두개로 나눌 수 있는 모든방법으로 나눴을 때 그렇게 선거구가 나뉠 수 있는 지 검증하는 것은 

시간이 걸리니까 그 방법으로 나눴을 때 값이 현재 답보다 유망한가를 먼저 계산 후, 검증을 나중에 한다. 그리고 검증이

되었을때 그 값을 답으로 바꾸고 다음 방법으로 넘어가는 방식으로 문제를 풀었다.

선거구를 나눌 수 있는 방법은 한 구역을 0번 선거구에 넣을것인가 1번선거구에 넣을것인가를 정하는 재귀함수를 

사용하였으며, 모든 지역이 두 선거구로 나눠진후 검증은 각각에 선거구에 대해서 DFS로 탐색하여 한 선거구안에 있는

모든 구역을 탐색할 수 있으면 검증은 완료 된다.

 

https://github.com/MingNine9999/algorithm/blob/master/Problems/boj17471.cpp

MingNine9999/algorithm