[백준 17471번] 파이썬 - 게리맨더링

백준 17471 - 게리맨더링

시간 제한 0.5초(추가 시간 없음), 메모리 제한 512MB

# 조건

• 백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다.
• 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다.
• 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.
• 백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다.
• 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다.
• 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다.
• 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다.
• 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.
• 아래 그림은 6개의 구역이 있는 것이고, 인접한 구역은 선으로 연결되어 있다.

• 아래는 백준시를 두 선거구로 나눈 4가지 방법이며, 가능한 방법과 불가능한 방법에 대한 예시이다.

• 공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이를 최소로 하려고 한다.
• 백준시의 정보가 주어졌을 때, 인구 차이의 최솟값을 구해보자.

입력

• 첫째 줄에 구역의 개수 N이 주어진다.
• 둘째 줄에 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 주어진다.
• 인구는 공백으로 구분되어져 있다.
• 셋째 줄부터 N개의 줄에 각 구역과 인접한 구역의 정보가 주어진다.
• 각 정보의 첫 번째 정수는 그 구역과 인접한 구역의 수이고, 이후 인접한 구역의 번호가 주어진다.
• 모든 값은 정수로 구분되어져 있다.
• 구역 A가 구역 B와 인접하면 구역 B도 구역 A와 인접하다.
• 인접한 구역이 없을 수도 있다.

출력

• 첫째 줄에 백준시를 두 선거구로 나누었을 때, 두 선거구의 인구 차이의 최솟값을 출력한다.
• 두 선거구로 나눌 수 없는 경우에는 -1을 출력한다.

제한

• 2 ≤ N ≤ 10
• 1 ≤ 구역의 인구 수 ≤ 100

# 접근 방법

• 전체 구역의 수가 최대 10이므로 브루트 포스로 풀어주어도 된다.
• itertools의 combination을 이용하여 한 선거구에 들어갈 수 있는 조합의 경우를 구해준다.
  • 이 때, 조합의 길이는 N//2 + 1까지만 해준다.
  • 선거구를 양분할 하기 때문에 N//2 + 1의 길이가 넘어가면 중복되기 때문이다.
  • 즉, a조합이 1, 2 일 때 b조합은 3 4 5 6이 되므로
  • a조합이 3 4 5 6 인 것과 b조합이 1 2 인 경우를 중복 체크하게 된다.
• combination으로 구한 A 선거구의 구역을 제외한 나머지는 B선거구에 담아준다.
• 이후 각 선거구가 연결되어 있는지 bfs를 통하여 확인하고 최솟값을 갱신해 나가면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from itertools import combinations  
from collections import deque  

def bfs(group):  
    q = deque()  
    q.append(group[0])  
    visited = [False] * (N+1)  
    visited[group[0]] = True  
    cnt = population[group[0]]  
    while q:  
        now = q.popleft()  
        for k in region[now]:  
            if k in group and not visited[k]:  
                q.append(k)  
                visited[k] = 1  
                cnt += population[k]  

    for g in group:  
        if not visited[g]:  
            return 0  
    return cnt  

N = int(input())  
population = [0] + [*map(int, input().split())]  
region = [[] for _ in range(N+1)]  
for i in range(N):  
    query = [*map(int, input().split())]  
    region[i+1] = query[1:]  

result = float('inf')  
# 선거구를 2개로 나누므로 N//2+1개를 넘어가면 중복된 계산을 하게된다.  
for i in range(1, N//2+1):  
    for comb in combinations(range(1, N+1), i):  
        A = list(comb)  
        B = []  
        for j in range(1, N+1):  
            if not j in A:  
                B.append(j)  
        val1, val2 = bfs(A), bfs(B)  

        if val1 and val2:  
            result = min(result, abs(val1 - val2))  

print(result if not result == float('inf') else -1)