[BOJ] 17471 게리멘더링

import itertools
import collections

def bfs(arr,team):
    q=collections.deque()
    q.append(arr)
    cnt=1
    visited[arr]=True
    while q:
        node=q.popleft()
        for k in graph[node]:
            if visited[k]==False and k in team:
                visited[k]=True
                q.append(k)
                cnt+=1
    if cnt==len(team):
        return True
    else:
        return False
 

N=int(input())
arr=list(range(1,N+1))
people=[0]

people.extend(list(map(int,input().split())))
graph=[[]]
people_total=sum(people)
for i in range(N):
    temp=list(map(int,input().split()))
    graph.append(temp[1:])
min_number=999999999999999
for i in range(1,N//2+1):
    b=itertools.combinations(arr,i)
    for k in b:
        a_team=list(k)
        b_team=list(set(arr)-set(k))
        
        visited=[False]*(N+1)
        
        if bfs(a_team[0],a_team) and bfs(b_team[0],b_team):        
            a_team_sum=0
            for tt in a_team:
                a_team_sum+=people[tt]
            b_team_sum=people_total-a_team_sum
            if abs(b_team_sum-a_team_sum)<=min_number:
                min_number=abs(b_team_sum-a_team_sum)       
    if min_number==0:
        break
if min_number>1000:
    print(-1)
else:
    print(min_number)

기본적인 그래프 이론이다.

 

기본 컨셉은 combination을 이용해 전체 N에서 절반만큼만 구한다. 이유는 조합은 n-k 와 k일떄의 조합은 같기 때문이다.

그렇게 구한 조합에서 set을 이용해서 서로 뺄샘으로 a_team과 b_team을 구하고, 경로탐색을 통해 서로 이어진 숫자와 팀의 길이와 같은지 구분을 하고, 게리멘더링이 성립되는경우에 두 팀간의 격차를 구하고, 최소값을 갱신해준다.