백준 17471 게리맨더링 (파이썬)

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

17471번: 게리맨더링

구역을 한 개로 나눌 때부터 n//2개로 나눌 때까지 각 경우를 모두 검사한다

n이 5일 때를 예로 들면 구역을 2,3으로 나누는 경우와 3,2로 나누는 경우는 같기 때문에 n//2 까지만 확인하면 된다

 

1. dfs로 선거구를 1개부터 n//2개 까지 뽑는다

2. 목표 개수만큼 지역을 선정하면 각 선거구가 이어져있는지 bfs로 확인한다

3. 이어져있지 않다면 bfs에서 0을 반환하고 이어져있으면 해당 선거구의 인구를 반환한다

4. 인구수 차의 최소값을 계속 기록해나간다

5. 마지막에 조건대로 출력

from collections import deque
import sys

input = sys.stdin.readline

def bfs(g):
    q = deque()
    check = [0 for _ in range(n)]
    q.append(g[0])
    check[g[0]] = 1
    cnt, ans = 1, 0
    while q:
        x = q.popleft()
        ans += people[x]
        for nx in a[x]:
            if nx in g and not check[nx]:
                check[nx] = 1
                cnt += 1
                q.append(nx)
    if cnt == len(g):
        return ans
    else:
        return 0

def dfs(cnt, x, end):
    global min_ans
    if cnt == end:
        g1, g2 = deque(), deque()
        for i in range(n):
            if c[i]:
                g1.append(i)
            else:
                g2.append(i)
        ans1 = bfs(g1)
        if not ans1:
            return
        ans2 = bfs(g2)
        if not ans2:
            return
        min_ans = min(min_ans, abs(ans2 - ans1))
        return

    for i in range(x, n):
        if c[i]:
            continue
        c[i] = 1
        dfs(cnt+1, i, end)
        c[i] = 0

n = int(input())
people = list(map(int, input().split()))

a = [[] for _ in range(n)]
for i in range(n):
    x = list(map(int, input().split()))
    for j in range(1, x[0]+1):
        a[i].append(x[j]-1)

min_ans = sys.maxsize
for i in range(1, n // 2 + 1):
    c = [0 for _ in range(n)]
    dfs(0, 0, i)

if min_ans == sys.maxsize:
    print(-1)
else:
    print(min_ans)