Bakejoon 17471. 게리맨더링 / Python

17471. 게리맨더링

난이도 : 골드 3
소요 시간 : 20분
날짜 : 2024.01.02
언어 : 파이썬
알고리즘 유형 : 그래프이론, bfs, dfs, 조합

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 각각의 인구가 있는 구역이 있음.
2. 구역을 두 선거구로 나누어야 함.
   • 같은 선거구에 속한 구역은 항상 연결되어있어야 함.
   • 한 선거구에는 최소 1개 이상의 구역이 있어야 함.
3. 각 선거구의 인구의 차이를 최소로 하기

2. 해결 방식

1. 구역의 개수가 최대 10밖에 안되어서 그냥 완전탐색을 하기로 했다.
2. 가능한 모든 선거구의 조합을 구해서 확인한다.
   • 먼저 선거구가 연결되어있는지 확인 : 기본적인 bfs로 해결
   • 연결되어있다면 최소값 갱신

3. 정답 코드

import sys;input = sys.stdin.readline
from itertools import combinations
from collections import deque as dq

n = int(input())
populations = list(map(int, input().split()))
arr = [[0] * n for _ in range(n)]

for i in range(n):
    inp = list(map(int, input().split()))
    num = inp[0]
    for j in range(1, num + 1):
        arr[i][inp[j] - 1] = 1
        arr[inp[j] - 1][i] = 1

inf = 1e10
res = inf
total = sum(populations)

def sol(left:list):
    global res
    right = [i for i in range(n) if i not in left]

    if len(left) in [0, n]:return
    if not check(left, len(left)):return
    if not check(right, len(right)):return

    res = min(res, abs(total - 2 * sum([populations[i] for i in left])))


def check(x:list, d:int):
    q = dq()
    visit = [0] * len(x)
    visit[0] = 1
    q.append(0)

    while q:
        now = q.popleft()
        for i in range(len(x)):
            if visit[i] or not arr[x[now]][x[i]]:continue
            visit[i] = 1
            q.append(i)

    return False if 0 in visit else True


for i in range(1 + n // 2):
    for com in combinations([j for j in range(n)], i):
        sol(list(com))

print(res if res != inf else -1)