boj 17471 게리멘더링

같은 시에서 각 선거구를 2개로 나눌려고 한다.
각 선거구끼리는 이어져 있어야한다.
나눌 때 인구수의 차이가 최소로 만들고 싶다.

각 조합을 만들어서 두 개의 그룹으로 나눈다.
두 그룹을 bfs를 돌려 연결이 되어있는지 판단.
두 그룹 모두 이어져 있다면 그 인구수의 절댓값을 계산
그 후 최소인지 판단.
두 그룹으로 나올 수 있는 경우의 수를 모두 bfs돌려도 이어질 수 없다면 -1 출력.

from itertools import combinations
from collections import deque

def bfs(group):
    queue = deque([group[0]])
    visited = [0] * (n+1)
    visited[group[0]] = 1
    count, sum_people = 1, populations[group[0]]
    while queue:
        a = queue.popleft()
        for i in graph[a]:
            if i in group and visited[i] == 0:
                queue.append(i)
                visited[i] = 1
                count += 1
                sum_people += populations[i]
    if count == len(group):
        return sum_people
    return False



n = int(input())

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

result = float('inf')

for i in range(1, n//2 + 1):
    comb = list(combinations(range(1, n+1), i))
    for group in comb:
        group1 = list(group)
        group2 = [i for i in range(1, n+1) if i not in group1]
        pop1 = bfs(group1)
        pop2 = bfs(group2)
        if pop1 and pop2:
            result = min(result, abs(pop1 - pop2))

if result == float('inf'):
    print(-1)
else:
    print(result)