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

문제

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

17471번: 게리맨더링

---

문제 요약

1번부터 N번까지 N개의 구역으로 나누어진 지역을 두 개의 선거구로 나눈다,

+ 선거구는 구역을 적어도 하나 포함해야 한다.

+ 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다.

(구역 A에서 구역 B로 갈 수 있을 때, 두 구역이 연결되어 있다고 한다.) 

 

공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이의 최솟값을 출력한다.

---

코드

from itertools import combinations as cb
from collections import deque, defaultdict

def bfs(List):
    start = List[0]
    q = deque([start])
    visited = set([start]) # 방문한 노드들의 집합
    _sum = 0 # 방문한 노드들의 인구 수
    while q:
        num = q.popleft()
        _sum += population[num]
        for i in graph[num]:
            if i not in visited and i in List:
                q.append(i)
                visited.add(i)
    return _sum, len(visited) # 방문한 노드들의 인구 수와 방문한 노드 수 반환

n = int(input()) 
# 구역의 개수

population = list(map(int, input().split()))
# 구역 별 인구 수. population[i]는 i번 구역의 인구 수

graph = defaultdict(list) # 자동으로 빈 리스트가 생성되는 딕셔너리

result = float('inf') # 두 선거구의 인구 차이 최솟값
# 결과 값에 무한대 저장 ('inf'는 무한대를 나타내는 부동 소수점의 리터럴)

# graph key값에 구역 번호, value값 리스트에 인접한 구역의 번호 저장
for i in range(n):
    infor = list(map(int, input().split()))
    for j in range(1, infor[0] + 1):
        graph[i].append(infor[j] - 1) # 구역 번호를 0 ~ n - 1로 변환하여 저장

#print(graph)

for i in range(1, n//2 + 1): # 절반만큼만 조합을 구한다. (그 이상은 어짜피 같은 경우)
    combis = list(cb(range(n), i)) # 0 ~ n까지 중 i개를 요소 추출한 배열들
    for combi in combis:
        sum1, v1 = bfs(combi) # 1 선거구
        sum2, v2 = bfs([i for i in range(n) if i not in combi]) # 2 선거구
        if v1 + v2 == n: # 모든 노드가 방문되었는지 확인
            result = min(result, abs(sum1 - sum2))

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

---

코드 설명

1. graph 딕셔너리에 key값 구역번호와 value값 인접한 구역들의 번호 배열을 저장한다.

+ 구역 번호를 0 ~ n - 1로 변환하여 저장한다.

 

2. mCn = mCm-n이 성립하므로 절반만큼만 조합을 구하여 선거구를 나눈다.

+ n개의 구역들 중 i개의 구역을 뽑아 1 선거구, 나머지 구역들을 2 선거구로 정한다.

 

3. bfs 함수를 통해 BFS탐색을 진행하며 방문한 노드들의 인구 수와 방문한 노드 수를 찾는다.

+ 1 선거구와 2 선거구, 총 2번의 BFS 탐색을 진행한다.

 

4. 1 선거구의 방문 노드 수 + 2 선거구의 방문 노드 수가 n개라면, result값을 갱신한다. (result 초기값: 무한)

(모든 노드가 방문되어야 한다. 그렇지 않으면 2개의 선거구가 아니다.)

 

5. result값을 출력한다. (무한대라면, 즉 갱신되지 않았다면 -1을 출력한다.)