[bfs/백준] 17471번 : 게리맨더링

- 문제 : https://www.acmicpc.net/problem/17471

 

다들 쉽다고 하는데, 나한테는 쉽지 않은 문제다 

그래도 최대한 이해해서 로직을 작성해봤다 

Gold Level4 문제 

 

1. 임의로 두 지역을 나눈다 (combination 이용)

2. 각 지역이 모두 연결되었는지 확인 

3. 2번이 참이라면 각 지역의 인구 총합을 구한다 (get_total() 함수 이용)

4. 인구 총합 차이의 최솟값을 찾는다 

5. 최솟값 출력한다

 

data[a][b] = 1 -> a 노드와 b 노드가 서로 연결되었다는 의미 

 

- 정답 풀이 : 

import sys
from itertools import combinations
from collections import deque

input=sys.stdin.readline
n=int(input())
people=list(map(int,input().split()))
data=[[0]*n for _ in range(n)]

for i in range(n):
    _,*dsts = map(int,input().split())
    for dst in dsts:
        data[i][dst-1] = 1

#선거구가 연결되었는지 확인        
def is_connected(nodes):
    queue=deque()
    visit=[0]*n
    queue.append(nodes[0])
    visit[nodes[0]]=1
    
    while queue:
        x=queue.popleft()
        for i in range(n):
            if not visit[i] and i in nodes and data[x][i]==1:
                visit[i]=1
                queue.append(i)
                
    return visit.count(1) == len(nodes)       

def get_total(nodes):
    total = 0
    for node in nodes:
        total += people[node]
        
    return total        

X = {i for i in range(n)}
flag = False
answer = 10**9

for i in range(1, n//2+1):
    #튜플로 하는 이유?
    AS = tuple(combinations(X,i))
    for A in AS:
        #딕셔너리에 difference??
        B = list(X.difference(A))
        #두 선거구가 연결돼있다면, 각 인구수 합의 차이 구함
        if is_connected(A) and is_connected(B):
            answer = min(answer, abs(get_total(A) - get_total(B)))
            flag = True
            
if not flag:
    print(-1)                      
else:
    print(answer)