https://www.acmicpc.net/problem/17471
삼성A형 기출문제이다.
bfs에 관한 문제.
최대 10개까지 구역이 있으니 완전탐색으로 두개의 그룹을 나누어 계산하는 것이라 생각했다.
절반이상을 넘어가면 그룹이 차이가 없기 때문에 그룹을 나누는 과정에서 n//2 + 1까지의 범위만 탐색하면 된다.
그 그룹이 연결되있지 않다면 0을 반환하고 bfs를 통해서 연결되있는것을 확인한다면 인구수를 반환하도록 하였다.
from collections import deque
from itertools import combinations
n = int(input())
population = list(map(int,input().split()))
population = [0] + population
graph = [[] for i in range(n+1)]
for i in range(1,n+1):
lst = list(map(int,input().split()))
for j in range(1,len(lst)):
graph[i].append(lst[j])
answer = 10000
def bfs(area):
queue = deque([area[0]])
visited = [0 for _ in range(n+1)]
cnt, ans = 1,0
visited[area[0]] = 1
while queue:
x = queue.popleft()
ans += population[x]
for e in graph[x]:
if e in area and not visited[e]:
visited[e] = 1
cnt += 1
queue.append(e)
if cnt == len(area):
return ans
else:
return 0
for i in range(1,n//2 + 1):
area_combination = list(combinations(range(1,n+1),i))
for area in area_combination:
area = list(area)
area_set = set(area)
area2 = set([j for j in range(1,n+1)])
area2 = area2 - area_set
area2 = list(area2)
sum1 = bfs(area) ## 연결이 안되어 있다면 0
sum2 = bfs(area2)
if sum1 == 0 or sum2 == 0:
continue
answer = min(answer, abs(sum1 - sum2))
if answer == 10000:
print(-1)
else:
print(answer)