[백준] 17471번 게리멘더링 (파이썬)

난이도 : GOLD IV

문제링크 : https://www.acmicpc.net/problem/17471

문제해결 아이디어

• 조합을 통해서 선거구를 나눈다. ex) (1,2,3),(4,5,6)
• bfs를 통해 해당 선거구가 연결 되어있는지 확인.
• 각각의 선거구가 연걸되어있다면 최솟값 비교

소스코드

from itertools import combinations
from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

population = [0] + list(map(int, input().split()))

graph = [[] for _ in range(n + 1)]

for i in range(1, n + 1):
    arr = list(map(int, input().split()))[1:]
    graph[i].extend(arr)

INF = int(1e9)

num = [i for i in range(1, n + 1)]


def bfs(arr):
    visited = [False] * (n + 1)
    q = deque()
    q.append(arr[0])
    visited[arr[0]] = True

    while q:
        x = q.popleft()
        for i in graph[x]:
            if not visited[i] and i in arr:
                q.append(i)
                visited[i] = True
    for i in arr:
        if visited[i] == False:
            return False
    return True


ans = INF

for i in range(1, n):
    for combi in combinations(num, i):
        another = []
        for j in num:
            if j not in combi:
                another.append(j)

        if bfs(combi) and bfs(another):
            p1 = p2 = 0
            for i in combi:
                p1 += population[i]
            for i in another:
                p2 += population[i]
            ans = min(ans, abs(p1-p2))
if ans == INF:
    print(-1)
else:
    print(ans)