[python] 백준 17471 게리맨더링

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

17471번: 게리맨더링

 

문제 해결

• 삼성 A형 기출문제
• 딱 봐도 완전탐색 문제이다.(2 ≤ N ≤ 10, 1 ≤ 구역의 인구 수 ≤ 100)
• 문제는 combination을 사용하여 모든 경우의 수를 다 고민을 해야하나인데... 맞다. 1개부터 n//2 개까지 선거구를 뽑은 다음 다 연결 되었는지 확인하고 나머지 선거구끼리도 모두 연결되었는지 확인해야한다.
• 모두 연결이 되면 두 집단의 인구 차이를 이전과 비교해서 작은 값을 저장한다.
• 삼성은 itertools 사용 못하는 걸로 알고있는데 따로 연습해가야하나?

CODE

import sys
from collections import deque
INF = sys.maxsize
def combinations(array,cnt):
    result = []
    if cnt ==0:
        return [[]]
    for i in range(len(array)):
        elementary = array[i]
        rest_array = array[i+1:]
        for c in combinations(rest_array,cnt-1):
            result.append([elementary]+c)
    return result
def bfs(v):
    start = v[0]
    que = deque()
    que.append(start)
    visited = [-1]*(n+1)
    visited[start] = 1
    cnt = 1
    total = 0
    while que:
        now = que.popleft()
        total += people[now]
        for next in graph[now]:
            if visited[next] == -1 and next in v:
                que.append(next)
                visited[next] = 1
                cnt += 1
    return total, cnt
if __name__=='__main__':
    n = int(input())
    people = [0]+ list(map(int,input().split()))
    graph = [[]]
    for i in range(1,n+1):
        _, *A = map(int, input().split())
        graph.append(A)
    cities = [i for i in range(1,n+1)]
    answer = INF
    for i in range(1,n//2+1):
        comb = list(combinations(cities,i))
        for c in comb:
            total1, cnt1 = bfs(c)
            total2, cnt2 = bfs([i for i in range(1,n+1) if i not in c])
            if cnt1+cnt2 == n:
                answer = min(answer,abs(total1-total2))
    print(answer if answer != INF else -1)