boj.kr/17471 게리멘더링 (gold4) 파이썬 풀이

1. 첫번째 선거구의 조합을 모두 추출하고 아래를 반복

1.1. 첫번째 선거구의 조합과 그 외 나머지 선거구의 조합을  bfs, dfs 방식 중 하나로 순회해 가능한 조합인지 검사

1.2. 가능한 조합이라면 두 선거구의 인구수 차를 저장

2. 두 선거구의 인구수 차 중 최소값을 출력, 가능한 조합이 없으면 -1을 출력

 

N = int(input())
nums = [0] + list(map(int, input().split()))
adj = [0] + []
for _ in range(N):
    adj.append(list(map(int, input().split()))[1:])

from collections import deque
def bfs(nodes):
    dq = deque()
    dq.append(nodes[0])
    nodes.remove(nodes[0])
    while dq:
        cur = dq.popleft()
        for nxt in adj[cur]:
            if nxt in nodes:
                dq.append(nxt)
                nodes.remove(nxt)
    return len(nodes) == 0

import sys
sys.setrecursionlimit(10**6)

def dfs(nodes, node):
    cur = node
    nodes.remove(cur)
    for nxt in adj[cur]:
        if nxt in nodes:
            dfs(nodes, nxt)
    return len(nodes) == 0

from itertools import combinations

diff = []
nodes = [x for x in range(1, N+1)]
for i in range(1, N):
    for combi in combinations(nodes, i):
        tot = 0
        if dfs(list(combi), combi[0]): #bfs(list(combi)):
            rest = [x for x in nodes if x not in list(combi)]
            if dfs(rest, rest[0]): #bfs(rest):
                for c in list(combi):
                    tot += nums[c]
                diff.append(abs(tot - (sum(nums)-tot)))

if len(diff) == 0:
    print(-1)
else:
    print(min(diff))

 

bfs, dfs 방식 모두 가능하나 PyPy3 으로 제출 시에는 메모리 초과하지 않으려면 bfs 방식을 사용해야 한다.