백준 17471 게리맨더링

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)