[백준] 17471. 게리맨더링 풀이 (Python)

17471번: 게리맨더링

 

접근한 방법

이 문제를 풀기 위해선 두 가지 과정이 필요합니다.

1. 선거구를 나눌 두 개의 조합

2. 각 조합을 탐색하여 서로 연결되어 있는 지 확인

 

먼저 두 개의 조합(A, B)으로 나누기 위해서는 1개 조합, 2개 조합, ... (N / 2)개 조합을 먼저 구한 후(A) 전체 조합에서 A 원소들을 빼준 것을 (B)로 정합니다.

 

예를 들면 A = [1, 2, 3, 4]의 조합은

1개 조합일 때

-> A = 1. B = [1, 2, 3, 4] - A = 2, 3, 4

-> A = 2. B = [1, 2, 3, 4] = A = 1, 3, 4 

... 로 이루어지고

2개 조합일 때

-> A = 1, 2. B = [1, 2, 3, 4] - A = 3, 4

-> A = 1, 3. B = [1, 2, 3, 4] - A = 2, 4

... 로 이루어집니다.

 

이 때 N이 아니라 N / 2개 조합까지만 구하는 이유는 중복이 일어나기 때문입니다.

이러한 방식으로 두 개 선거구 조합을 만들고 각 조합에 대하여 BFS 탐색을 시도합니다.

각 조합의 첫번째 원소를 시작점으로 잡아, 현재 확인 중인 구역과 연결되어 있는 구역들이 선거구에 포함되어 있다면 방문 횟수를 카운트합니다.

 

두 선거구를 모두 탐색하여 나온 방문횟수의 합이 전체 구역 수와 일치하다면 두 선거구는 나눌 수 있는 선거구가 됩니다.

두 선거구의 인구수 차이의 절댓값이 기존 결괏값보다 적으면 갱신해주는 방식으로 구현합니다.

 

 

Python

import sys
input = sys.stdin.readline

from itertools import combinations
from collections import deque

n = int(input())
arr = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n + 1)]

# 연결관계 그래프 생성
for i in range(1, n + 1):
    t = list(map(int, input().split()))
    graph[i].extend(t[1:])

# 두 선거구로 나누어진 조합 생성
def get_combinations(lists):
    results = []
    for i in range(1, n+ 1):
        for comb in combinations(lists, i):
            results.append((comb, tuple(set(lists) - set(comb))))
    return results

# 연결여부 확인을 위한 BFS 탐색
def bfs(area):
    s = area[0] # 시작점
    q = deque([s])
    visited = [0] * (n + 1)
    visited[s] = 1
    vcnt, cost = 1, 0 # 방문한 횟수, 방문구역 인구 누계
    while q:
        v = q.popleft()
        cost += arr[v]
        # 현재 구역과 연결된 구역들을 확인
        for i in graph[v]:
            # 구역을 방문하지 않았고 선거구(area)에 연결되어 있다면
            if not visited[i] and i in area:
                visited[i] = 1
                vcnt += 1
                q.append(i)
    return vcnt, cost

result = 1e9
for area in get_combinations([i for i in range(1, n + 1)]):
    print(area)
    a_vcnt, a_cost = bfs(area[0])
    b_vcnt, b_cost = bfs(area[1])
    # 두 선거구에 방문한 횟수의 합이 모든 구역 수와 같으면 결괏값 갱신
    if a_vcnt + b_vcnt == n:
        result = min(result, abs(a_cost - b_cost))

print(-1 if result == 1e9 else result)