백준 게리맨더링 파이썬

https://www.acmicpc.net/problem/17471

from itertools import combinations
from pprint import pprint
# 좌표와 양 진형 1, 2
def DFS(x, flag):
    visit[x] = flag
    for y in adj[x][1:]:
        if visit[y]: continue
        # 뽑은 조합의 것이 아닐때
        if flag == 1:

            if y not in c: continue
        else:
            if y in c: continue
        DFS(y, flag)

N = int(input())
arr = list(map(int, input().split()))
adj = [[]] + [list(map(int, input().split())) for _ in range(N)]
num = [i for i in range(1, N+1)]
# pprint(adj)
com = [list(combinations(num, i)) for i in range(1, N)]
# pprint(com)
ans = 1<<31
for co in com:
    # pprint(co)
    # 선택된 조합 뽑는 다
    for c in co:
        # pprint(f'c {c}------------')
        visit = [False] * (N + 1)
        DFS(c[0], 1)
        if visit.count(True) == len(c):
            for i in range(1, N+1):
                if visit[i]:continue
                DFS(i, 2)
                break
        if visit.count(False) == 1:
            # print(visit)
            tmp = 0
            for cc in c:
                tmp += arr[cc-1]

            ans = min(ans, abs(sum(arr) - 2 * tmp))

print(ans if ans != 1<<31 else -1)

알고 감 회복..중
프로젝트를 하니 알고에 신경을 들 쓰게 된다
간만에 푸니 코딩 스타일이 좀 바뀌었다
일단 과거엔 순열, count 모두 직접 구현 했었는 데 지금은 좋은 게 좋은 거다 하고 넘어가고 있다.