[문제풀이-백준] 17471. 게리맨더링

풀이

최소 신장 트리를 이용해야한다는 고정 관념때문에 힘들었던 문제다. 또한, 조합을 만들어야 하는데 순서대로 세워두고 처음부터 끊어서 이상한 조합을 만들었다. 확실하게 검증이 끝난 후에 코드로 구현해야하는 것을 명심해야한다.

알고리즘

조합 + dfs

아이디어

1. 1개부터 N//2까지 조합을 만든다. N//2+1부터는 1~N//2의 짝이기 때문에 구할 필요가 없다.
2. 만들어진 조합의 경우를 하나하나 left로 두고 right를 찾는다.
3. 만들어진 left와 right에서 각각 dfs를 수행한다.
4. 각각의 경우에서 인구 수를 구하고, 모든 지역이 포함됐는지 확인한다.
5. 포함됐다면, 인구의 차이를 answer와 비교한다.

코드

처음 푼 코드

from itertools import combinations

def dfs(here, cnt, cand):
    stack = [here]
    while stack:
        here = stack.pop()
        if visited[here]: continue
        visited[here] = 1
        cnt += people[here]
        for next in adj[here]:
            if not visited[next] and next in cand:
                stack.append(next)
    return cnt

N = int(input())
people = [0] + list(map(int,input().split()))
adj, answer = {}, 10000
for i in range(1, N+1):
    info = list(map(int,input().split()))
    adj[i] = []
    for j in range(1, info[0]+1):
        adj[i].append(info[j])

for i in range(1,N // 2 + 1):
    comb = list(combinations(range(1,N+1), i))
    for left in comb:
        left = list(left)
        right = []
        for j in range(1,N+1):
            if j in left: continue
            right.append(j)
        visited = [0] * (N+1)
        l_cnt = dfs(left[0], 0, left)
        r_cnt = dfs(right[0], 0, right)
        for i in range(1, N+1):
            if not visited[i]: break
        else:
            diff = abs(l_cnt - r_cnt)
            answer = min(diff, answer)

if answer == 10000: print(-1)
else: print(answer)

다시 풀어본 코드

from itertools import combinations
from collections import deque

def check_ward(here, cities):
    visited = [False] * N
    visited[here] = True
    deq = deque([here])
    people = cities_people[here]
    while deq:
        h = deq.popleft()
        for next in range(N):
            if not visited[next] and adj[h][next] and next in cities:
                visited[next] = True
                deq.append(next)
                people += cities_people[next]
    for city in cities:
        if not visited[city]: return 0
    return people


N = int(input())
cities_people = list(map(int,input().split()))
adj = [[0] * N for _ in range(N)]
for start in range(N):
    info = list(map(int,input().split()))
    for end in info[1:]:
        end -= 1
        adj[start][end] = 1
        adj[end][start] = 1

half = N // 2
answer = 9876543210
for perm_size in range(1,half + 1):
    perm = list(map(list,combinations(range(N), perm_size)))
    for cities1 in perm:
        cities2 = []
        for city in range(N):
            if city in cities1: continue
            cities2.append(city)
        peoples1 = check_ward(cities1[0], cities1)
        peoples2 = check_ward(cities2[0], cities2)
        if peoples1 and peoples2:
            diff = abs(peoples1 - peoples2)
            answer = min(diff, answer)

if answer == 9876543210: print(-1)
else: print(answer)