[백준] 17471번 : 게리맨더링

17471번: 게리맨더링

해당문제는 문제를 푸느라 굉장히 고생을 했습니다.

1. A구역, B구역 으로 나눌 수 있는 경우의 수를 모두 구한다.
   1. A,B 구역을 나누는 방법은 저는 재귀를 통하여 경우의 수를 만들었습니다.
   2. 파이썬의 조합 라이브러리를 사용 할 수 있었지만 사용하지 않았습니다.
   3. A,B 구역을 나눌때 예를들어 N이 6일때 {1,2,3) {4,5,6}와 {4,5,6}, {1,2,3} 이 중복되지 않도록 만듭니다.
   4. 또한 순열이 아닌 조합으로 만들어야합니다.
2. A구역, B구역으로 각각 잘 나누어졌는지 확인한다.
   1. A, B 구역으로 잘 나누었는지 확인하는 방법은 BFS를 활용 하였습니다.
   2. 팀에서 특정한 점에서 BFS를 했을때 다른 팀을 거쳐서 가지않고 우리팀을 갈 수 때이어야 합니다.
3. A구역, B구역의 인구수의 차이를 구한다.
   1. 반복문을 돌리면서 인구수 차이를 구합니다.

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
people = [0] + list(map(int, input().split()))
graph = [[] for _ in range(N+1)]
for i in range(1, N+1):
    temp = list(map(int, input().split()))
    if temp[0] > 0: # 간선의 개수가 0 이상일 경우
        for n in temp[1:]:
            graph[i].append(n)

def is_team(team):
    queue = deque()
    queue.append(team[0])
    visit = [False for _ in range(N+1)]
    for k in range(N+1):
        if k not in team:
            visit[k] = True
    visit[team[0]] = True

    while queue:
        new_n = queue.popleft()
        for new_n2 in graph[new_n]:
            if new_n2 in team and not visit[new_n2]:
                visit[new_n2] = True
                queue.append(new_n2)

    if all(visit):
        return True
    else:
        return False

ans = sum(people)

def people_diff(team, team2):
    temp = 0
    temp2 = 0
    for n in team:
        temp += people[n]
    for n in team2:
        temp2 += people[n]

    return abs(temp - temp2)

def make_team(idx, team):
    global ans
    if team and team[0] > N // 2:
        return

    if N > len(team) > 0: # 모든 팀이 결성이 되면
        team2 = [i for i in range(1, N+1) if i not in team]
        if is_team(team) and is_team(team2):
            #print(team, team2)
            ans = min(people_diff(team, team2), ans)
            #print(ans)

    for n in range(idx, N + 1):
        if n not in team:
            team.append(n)
            make_team(idx + 1,team)
            team.pop()

make_team(1, [])
if ans == sum(people):
    print(-1)
else:
    print(ans)