17471: 게리맨더링

풀이 시간

• 1h 4m
• 30분 동안 고민하다가 감이 잘 안잡혀서 구글링.. brute force를 할 때 모든 경우를 고려해줘야하는 부분을 어떻게 시작해줘야할 지 가끔씩 감이 잘 안잡힌다. brute force 연습 더 많이 해야할듯

구현 방식

• N이 10보다 작기 때문에 brute force로 풀이가 가능하다
• 정말 모든 경우를 탐색해줘야하기 때문에, 선거구를 나누는 모든 경우를 고려해줘야한다
• • 1 + (N-1), 2 + (N-2), ... (N-1) + 1개의 경우를 모두 탐색 (1부터 N//2까지만 탐색해줘도 모든 경우가 탐색됨)
• • 각 경우마다 combinations()를 통해 고르는 모든 조합을 구함. 이 모든 조합을 다시 모두 탐색해주어야함
• • • comb, sub_comb로 나누어 bfs()를 시행하여 인구수를 구하고, 구하고자 하는 답인 diff 변수를 최솟값으로 update해줌
• bfs()를 탐색하는 과정에선 구역에 있는 노드들만 탐색하면서 인구수를 더해가야하기 때문에 comb를 set으로 변환하여 nx in comb 조건을 만족할 때 다음 노드로 탐색을 진행하도록 해주었다
• • • 한 구역에 있는 노드들은 연결되어있어야 하기 때문에, bfs()에서 visit set의 length도 함께 반환해주어 이를 확인하는 절차가 추가적으로 필요하다
• 인접리스트를 생성하는 부분에서 collections.defaultdict(list)를 사용하여 좀 더 코드를 간편하게 작성함

코드

import sys
from collections import deque
from collections import defaultdict
from itertools import combinations

def bfs(comb):
    queue = deque([])
    visit = set()

    queue.append(comb[0])
    visit.add(comb[0])
    comb = set(comb)

    total = 0
    while queue:
        x = queue.popleft()
        total += population[x]

        for nx in A[x]:
            if (nx not in visit) and (nx in comb):
                queue.append(nx)
                visit.add(nx)

    return total, len(visit)


N = int(input())
population = list(map(int, sys.stdin.readline()[:-1].split()))

A = defaultdict(list)
for n in range(N):
    tmp = list(map(int, sys.stdin.readline()[:-1].split()))
    for i in range(1, tmp[0]+1):
        A[n].append(tmp[i]-1)

diff = 10e9
for i in range(1, N//2 +1): #선거구를 나누는 모든 경우
    combs = list(combinations(range(N), i))
    for comb in combs:
        total1, count1 = bfs(list(comb))

        sub_comb = []; set_comb = set(comb)
        for j in range(N):
            if j not in set_comb:
                sub_comb.append(j)
        total2, count2 = bfs(sub_comb)

        if count1 + count2 == N:
            diff = min(diff, abs(total1 - total2))

if diff == 10e9:
    print(-1)
else:
    print(diff)

결과