[백준 17471] 게리맨더링(Python)

1. 요약

N개의 구역이있고, 각 구역에 시민들이 살고 있다. 그리고 구역을 묶어서 2개의 선거구를 만들어야한다. 선거구를 만들 때 규칙은 다음과 같다.

• 각 구역은 두 선거구 중 반드시 하나에만 포함되어야한다.
• 선거구는 적어도 구역 하나를 포함해야한다.
• 선거구에 포함된 구역들은 모두 연결되어야한다.(i.e. 구역 A에서 인접한 구역을 통해서 또는 바로 구역 B로 갈 수 있을 때, A구역 B구역은 연결되었다고 한다.)

2개의 선거구를 만들 때, 두 선거구 인구 차이의 최소값을 구해야한다.

2. 아이디어

N이 작은 수로 주어지므로 완전탐색으로 이용하여 구현한다.

두 개의 선거구를 각각 A, B라고 하자

A 선거구에 m(0<m<=n//2)개의 구역을 할당하는 경우들을 조합을 이용하여 구한다.

이후, 위의 결과를 이용하여 B 선거구에는 N-m개의 구역을 할당하는 경우를 구한다.

m의 범위가 위와 같은 이유는 A 선거구에서 m개의 구역을 할당하고, B 선거구에서 n-m개의 구역을 할당하여 나온 인구수의 차이와 A 선거구에서 n-m개의 구역을 할당하고, B 선거구에서 m개의 구역을 할당하여 나온 인구수의 차이는 같기 때문이다. 따라서 m의 범위를 < n이 아닌 <= n//2로 줄여 중복을 피할 수 있다.

BFS를 이용하여 A 선거구 내 구역 연결 여부, B 선거구 내 구역 연결 여부를 확인한다.

A, B 모두 유효한 선거구이면, A 선거구내 인구와 B 선거구내 인구의 차이를 구한다.

가능한 차이값 중 가장 작은 것을 선택한다.(가능 한 값이 하나도 없으면 -1 출력)

3. 코드

import sys
from itertools import combinations
from collections import deque

n = int(sys.stdin.readline().rstrip())
people = list(map(int, sys.stdin.readline().rstrip().split()))
arr = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    _, *dsts = map(int, sys.stdin.readline().rstrip().split())
    for dst in dsts:
        arr[i][dst-1] = 1


def is_connected(nodes):
    q = deque()
    check = [False for _ in range(n)]
    q.append(nodes[0])
    check[nodes[0]] = True

    while q:
        node = q.popleft()

        for i in range(len(arr[node])):
            if arr[node][i] == 0: continue
            if i not in nodes: continue
            if not check[i]:
                check[i] = True
                q.append(i)

    return check.count(True) == len(nodes)

                
def get_total(nodes):
    total = 0
    for node in nodes:
        total += people[node]

    return total


cases = []
X = {i for i in range(n)}
INF = int(1e9)
ans = INF

for i in range(1, n//2+1):
    As = tuple(combinations(X, i))
    for A in As:
        B = list(X.difference(A))

        if is_connected(A) and is_connected(B):
            a_total = get_total(A)
            b_total = get_total(B)
            ans = min(ans, abs(a_total-b_total))

if ans == INF: print(-1)
else: print(ans)