[백준] 17471 게리맨더링 (파이썬)

골드 Ⅳ

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

17471번: 게리맨더링

 

📄 문제

• 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.
• 백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다.
• 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다.
• 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다.
• 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다.
• 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

 

공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이를 최소로 하려고 한다. 백준시의 정보가 주어졌을 때, 인구 차이의 최솟값을 구해보자.

 

---

💡 아이디어

• 구역의 개수가 최대 10개이므로 완전탐색이 가능하다.
• 모든 구역을 2 개의 선거구로 나눠야 한다.
  • 조합(combination)을 사용하여 경우의 수를 나눈다.
  • 첫 번째, 선거구는 combination으로 선택된 구역
  • 두 번째, 선거구는 전체 구역 중 combination으로 선택된 구역 제외한 구역

• 각 선거구에 포함되어 있는 구역이 모두 연결되어 있는지 확인해야 한다.
  • 너비우선탐색(BFS)으로 인접 그래프 탐색을 진행한다.
  • 두 구역이 모두 연결되어 있는지 확인한다.

• 각 선거구에 포함된 인구의 합을 구한다.
• 인구의 차이를 최솟값을 구한다.

 

---

모든 구역을 2 개의 선거구로 어떻게 나눌지 고민을 했다.

combination을 사용하지 않고 하는 방법은 없을까 생각했지만,,

완전 탐색이 가능한 문제이므로 combination을 사용했다.

 

📝 문제 풀이 (Code)

from itertools import combinations
import sys
input = sys.stdin.readline

# 1. 구역이 연결된 2개의 선거구로 나뉘어 지니?
# 2. 선거구의 인구 차이가 얼마니?

# 나눈 그룹이 연결되어있는지 확인
def bfs(v, group):
    # 방문 체크
    visited = set()
    visited.add(v)
    
    stack = [v]

    while stack:
        v = stack.pop()

        for w in graph[v]:
            # 선거구에 속하고 방문 안했으면 탐색
            if w in group and w not in visited:
                visited.add(w)
                stack.append(w)
    # 나눈 선거구와 연결되어있는 구역이 같은지 확인
    return visited == group


n = int(input())
population = list(map(int,input().split()))
graph = [[] for _ in range(n+1)]

# 인접한 구역의 정보 저장
for i in range(1,n+1):
    m, *tmp = list(map(int,input().split()))
    for j in range(m):
        graph[i].append(tmp[j])

# 구역 번호
area = range(1, n+1)
# 두번째 그룹 구할 때 활용
setArea = set(area)

# 최솟값 저장
minV = 100 * 10 + 1

# 조합으로 구역 나누기
# 두 그룹으로 나누기 때문에 N//2+1 이상으로 넘어가면 조합이 중복되어 똑같은 작업을 한다.
for k in range(1, n//2+1):
	# 첫번째 그룹
    for g1 in combinations(area, k):
        setG1 = set(g1)
        # 두번째 그룹
        setG2 = setArea-setG1
        g2 = list(setG2)
        # 2개의 구역으로 나뉜 각각의 선거구가 연결되어 있으면
        if bfs(g1[0], setG1) and bfs(g2[0], setG2):
            # 인구 차이 저장
            diff = 0

            for p1 in g1:
                diff += population[p1-1]

            for p2 in g2:
                diff -= population[p2-1]
                
            # 차이가 0이면 최소 경우 이므로 종료!
            if diff == 0:
                print(0)
                exit()

            # 최솟값 찾기
            minV = min(minV, abs(diff))
            
# 변동없으면 두 선거구로 나눌 수 없는 경우이다.
if minV == 1001:
    print(-1)
else:
    print(minV)

 

 

다른 구현 방법

아이디어는 같고 구현 방법이 조금 다르다.

• BFS 함수에서 방문 체크 방법이 다르다.
• 각 선거구 인구 수의 합을 구하는 방법이 다르다. (BFS 함수 내에서 일어난다.)

from itertools import combinations
import sys
input = sys.stdin.readline

# 1. 구역이 나뉘어 지니?
# 2. 인구 차이가 얼마니?

def bfs(v, group):
    # group으로 방문 체크
    stack = [v]
    total = 0
    while stack:
        v = stack.pop()
        # 인구수 더하기
        total += population[v-1]

        for w in graph[v]:
            # 선거구에 속하면 탐색
            if w in group:
                # 선거구에서 제거 (방문체크)
                group.remove(w)
                stack.append(w)

    # group에 구역이 남아있으면 구역이 모두 연결되어 있지 않음
    if group:
        return 0
    return total


n = int(input())
population = list(map(int,input().split()))
graph = [[] for _ in range(n+1)]

# 인접한 구역의 정보
for i in range(1,n+1):
    m, *tmp = list(map(int,input().split()))
    for j in range(m):
        graph[i].append(tmp[j])

# 조합으로 구역 나누기
area = range(1, n+1)
setArea = set(area)
minV = 100 * 10 + 1
# 두 그룹으로 나누기 때문에 N//2+1 이상은 조합이 중복되어 똑같은 작업을 한다.
for k in range(1, n//2+1):
    for g1 in combinations(area, k):
        setG1 = set(g1)
        setG2 = setArea-setG1

        totalG1 = bfs(setG1.pop(), setG1)
        totalG2 = bfs(setG2.pop(), setG2)
        if totalG1 and totalG2:
            # 인구 차이 저장
            diff = totalG1 - totalG2

            # 차이가 0이면 최소 경우 이므로 종료!
            if diff == 0:
                print(0)
                exit()

            # 최솟값 찾기
            minV = min(minV, abs(diff))

if minV == 1001:
    print(-1)
else:
    print(minV)