[알고리즘] 게리맨더링

먼저 방문자 수 900명을 축하합니다.  (정말 부족한 글인데도) 정보로 받아들일 수 있게끔, 쓰려고 노력하는데 잘 되지가 않네요. 

포인트

• 문제의 포인트는 2가지 입니다. (조합, BFS) 사실 이 조합이 구현 문제들에서 잘 나오더라구요.
• 또, 조합은 2개의 그룹으로 나누기 때문에, n//2+1 이라는 점도 알고 지나가셨으면 좋겠습니다. 
  
  
• 주요 흐름은 그룹 1을 재귀 적으로 찾고 포함하지 않는 그룹 1을 포함하지 않는 원소들의 집합인 그룹 2를 정의합니다.  그리고 BFS 를 통해서 연결되었음을 확인합니다. 만약 연결 되어 있지않으면 return 을 시켜서 상태 공간 트리에서 더이상 탐색을 하지 않도록 합니다. 

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

from collections import deque
import sys

input = sys.stdin.readline


def bfs(group: list) -> int:
	"""
	BFS 를 통해 탐색을 한다.
	탐색한 결과와 그 크기가 같다면
	:param group:
	:return:
	"""
	q = deque()
	q.append(group[0])
	
	visited = set()
	visited.add(group[0])
	
	cnt, result = 1, 0
	while q:
		x = q.popleft()
		result += people[x]
		for nx in data[x]:
			if nx in group and nx not in visited:
				visited.add(nx)
				q.append(nx)
				cnt += 1
	
	return result if cnt == len(group) else 0


def go(index: int, cnt: int, count_comb):
	global answer
	# 조합적인 방법으로 반을 나누어 생각한다.
	# 어차피 2개 이기 때문에 반만 해도 된다.
	if cnt == count_comb and index == n:
		result1 = bfs(group1)
		if not result1:
			return
		group2 = []
		for i in range(n):
			if i not in group1:
				group2.append(i)
		
		result2 = bfs(group2)
		if not result2:
			return
		
		answer = min(answer, abs(result2 - result1))
		return
	
	if index >= n:
		return
	
	group1.append(index)
	go(index + 1, cnt + 1, count_comb)
	group1.pop()
	
	go(index + 1, cnt, count_comb)


n = int(input())
people = list(map(int, input().split()))

data = [[] for _ in range(n)]
for i in range(n):
	x, *temp = list(map(int, input().split()))
	data[i].extend(list(map(lambda x:x-1, temp)))

answer = 987654321
for i in range(1, n // 2 + 1):
	group1 = []
	go(0, 0, i)

if answer == 987654321:
	print(-1)
else:
	print(answer)