[BOJ/Python] 17471. 게리맨더링

📌 문제

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

17471번: 게리맨더링

 

📌 문제 접근 방법

1. N개의 구역을 조합을 이용해서 2개의 선거구로 나눈다.
2. 각 선거구를 bfs를 통해 탐색해서 모든 구역에 방문할 수 있는지 체크한다.
   여기서, 선거구에 있는 구역만 탐색을 하는 것이 포인트! (w in group → 이걸 처리 안해줘서 실패가 나왔음!)
3. 2개의 선거구 모두 선거구 안의 모든 구역에 방문할 수 있다면, 인구 수의 차이를 구하고 최소값으로 갱신한다.

 

📌 코드

# 백준 17471 게리맨더링
from collections import deque
from itertools import combinations

def diff_pop(A, B):
    global min_pop

    A_pop = 0
    B_pop = 0

    for a in A:
        A_pop += population[a]
    
    for b in B:
        B_pop += population[b]
    
    min_pop = min(min_pop, abs(A_pop-B_pop))


def bfs(group):
    queue = deque()
    queue.append(group[0])

    visited = [0 for _ in range(N+1)]
    visited[group[0]] = 1

    while queue:
        v = queue.popleft()

        for w in section[v]:
            if w in group and visited[w] == 0:
                visited[w] = 1
                queue.append(w)
    
    for g in group:
        if visited[g] == 0:
            return False
    return True


N = int(input())
population = [0] + list(map(int, input().split()))

section = [[] for _ in range(N+1)]
for i in range(N):
    temp = list(map(int, input().split()))
    section[i+1] = temp[1:]

min_pop = float('inf')
for n in range(1, N//2 + 1):
    for combo in combinations([x for x in range(1, N+1)], n):
        A = combo
        B = [y for y in range(1, N+1) if y not in A]

        if bfs(A) and bfs(B):
            diff_pop(A, B)

if min_pop == float('inf'):
    min_pop = -1

print(min_pop)