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

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

# 게리멘더링
import sys
from collections import deque
MAX = sys.maxsize
input = sys.stdin.readline
N = int(input())
person = [0] + list(map(int, input().split()))
arr = [[] for _ in range(N+1)]
for i in range(1, N+1):
    temp = deque(map(int, input().split()))
    temp.popleft()
    arr[i] = list(temp)


def bfs(area):
    q = deque()
    visited = [False] * (N+1)
    q.append(area[0])
    visited[area[0]] = True
    temp = 0
    count = 1
    while q:
        node = q.popleft()
        temp += person[node]
        for nnode in arr[node]:
            if nnode in area and not visited[nnode]:
                visited[nnode] = True
                count += 1
                q.append(nnode)
    if count == len(area):
        return temp


def choose(n, count):
    global result
    if count == n:
        area1, area2 = [], []
        for i in range(1, N+1):
            if visited[i]:
                area1.append(i)
            else:
                area2.append(i)
        x, y = bfs(area1), bfs(area2)
        if x and y:
            result = min(result, abs(x-y))
        return
    for i in range(1, N+1):
        if not visited[i]:
            visited[i] = True
            choose(n, count+1)
            visited[i] = False


result = MAX
for i in range(1, N // 2 + 1):
    visited = [False]*(N+1)
    choose(i, 0)

if result == MAX:
    print(-1)
else:
    print(result)

 

백트랙킹, BFS

1. 인접리스트로 입력을 받는다

2. 백트랙킹으로 도시 분할(1개 ~ N // 2 +1개)

3. 분할한 도시로 BFS로 연결가능한지 체크 및 합 return

4. 두 지역의 인구 차이의 최소값을 result에 append

5. result 출력

 

 

처음 백트랙킹할 때, N개까지 반복했다가 시간초과가 나왔는데

생각해보니까 다른지역과 겹치기 때문에 반만 해도 괜찮았다.