[BaekJoon] 백준 17471번 게리맨더링

[BaekJoon] 백준 17471번 게리맨더링

 

🎈문제

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

💬설명

• 2 ≤ N ≤ 10 , 1 ≤ 구역의 인구 수 ≤ 100 
• 제한사항이 위와 같아 0.5초에도 충분이 돌릴 수 있는 양이라고 생각했기 때문에 조합 -> bfs를 이용해 풀어줬다.
• 문제 풀이 순서
  1. 1-N/2만큼의 조합을 구한다. (ex. N=4일때, 길이 1 + 길이 3, 길이 2 + 길이 2의 조합)
  2. 구한 조합을 가지고 각각에 대해, 총 2번 bfs를 돌린다.
  3. bfs를 돌았을 때 모든 노드가 2개의 선거구로 나뉠 수 있다면(연결되어 있다면) 인구수 차이의 최소값을 update한다. 

👩‍💻코드

# BaekJoon17471.py
from collections import deque
from itertools import combinations


def bfs(arr):
    global people, link
    start = arr[0]
    queue = deque([start])
    visited = set([start])
    num = 0

    while queue:
        value = queue.popleft()
        num += people[value]
        for i in link[value]:
            if i not in visited and i in arr:
                queue.append(i)
                visited.add(i)
    return num, len(visited)


N = int(input())  # 구역 개수
people = [0] + list(map(int, input().split()))  # 인구수 배열
link = [0 for _ in range(N + 1)]  # 연결된 구역들 리스트
result = float('inf')

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

for i in range(1, N // 2 + 1):
    combis = list(combinations(range(1, N + 1), i))
    for combi in combis:
        sum1, node1 = bfs(combi)
        sum2, node2 = bfs([i for i in range(1, N + 1) if i not in combi])
        # 두 선거구의 모든 노드가 연결되어 있는지 확인
        if node1 + node2 == N:
            result = min(result, abs(sum1 - sum2))

if result != float('inf'):
    print(result)
else:
    print(-1)

👉참고

https://cotak.tistory.com/66