[백준] 17471_게리맨더링

📕 문제

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

17471번: 게리맨더링

 

💡 풀이법

1. 1~N-1개의 조합을 만든다. 

(여기서 만든 조합은 한 선거구가 되고, 나머지 번호들이 다른 선거구가 된다)

2. for문을 돌며 구한 조합에 대해서 dfs를 돌린다. 우선  조합에 들어있는 번호를 visited에 담고, 방문할 때마다 visited에서 빼는 식으로 모두 방문가능한지 구한다. (dfs가 다 돌고 visited가 비었다면 조합에 있는 모든 구역이 인접한것)

3. dfs를 돌며 방문체크와 동시에 total에 선거구의 인구수를 더해서 합을 구한다.

4. 모두 방문 가능하다면 다른 선거구의 인구의 합(전체 인구수- total)과 현재 선거구의 차이(diff)를 구한다.

5. 차이가 ans보다 작다면 다름 선거구에 대해서 모두 인접한지 확인한다.

( 차이가 ans보다 작지 않다면 답이 될수 없기 때문에 두 선거구들이 각자 인접해있더라도 굳이 봐줄 필요가 없음)

6. 다른 선거구도 모두 인접하다면 그때 ans를 두 선거구의 인구수 차이로 바꾼다.

 

from itertools import combinations

def dfs(n):
    total = 0
    stack = [n]
    visited.remove(n)

    while stack:
        v = stack.pop()
        total += population[v]

        for j in node[v]:
            if j in visited:
                visited.remove(j)
                stack.append(j)
    return total

N = int(input())
population = [0] + list(map(int, input().split()))
population_sum = sum(population)
node  = {}
ans = 9999

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

area = [i for i in range(1, N+1)]
for i in range(1, N):
    for item in combinations(area, i):
        visited = list(item)
        t = dfs(visited[0])

        if not visited:
            diff = abs((population_sum - t)-t)

            if diff < ans:
                visited = list(set(area) - set(item))
                dfs(visited[0])

                if not visited:
                    ans = diff

if ans == 9999:
    print(-1)
else:
    print(ans)