[백준/dfs] 17471번: 게리맨더링(다시)

-문제: https://www.acmicpc.net/problem/17471

17471번: 게리맨더링

 

당최 무슨말인지 잘 모르겠는 문제다,, 

다시 공부해야겠다 

 

참고한 블로그 ​

-정답풀이:

 

import sys
from itertools import combinations
from collections import deque
input=sys.stdin.readline
n=int(input())
people=list(map(int,input().split()))
arr=[[0]*n for _ in range(n)]

for i in range(n):
    _,*dsts = map(int,input().split())
    for dst in dsts:
        arr[i][dst-1]=1
        
def bfs(nodes):
    q=deque()
    q.append(nodes[0])
    check=[False for _ in range(n)]
    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 bfs(A) and bfs(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)