백준 - 게리맨더링

문제 출처: https://www.acmicpc.net/problem/17471

17471번: 게리맨더링

 

선거구를 어떻게 조합해야 각 선거구끼리 연결되어있고, 선거구 내에서 개수는 상관없으므로 부분집합을 사용하였다.

전체적인 로직은,

1. 부분집합을 통한 선거구 나누기

2. 나눈 선거구가 유효한지 확인(특정 한 선거구 맛있으면 유효하지 않다.)

3. 유효하다면, 각 선거구 별 점수 구하기( 선거구 별로 재귀를 통한 점수 합산.)

4. 선거구 별 다시 한번 유효 확인(각 선거구는 서로 연결되어있으므로 만약 위에 3번에서 재귀 탐색 이후에 방문 배열에 하나라도 False, 즉 방문하지 않은 곳이 있다면 유효하지 않다.)

5. 각 선거구 별 점수 차이 최소값 갱신