코딩테스트 연습 - 게리맨더링

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

 

문제

백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

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

아래 그림은 6개의 구역이 있는 것이고, 인접한 구역은 선으로 연결되어 있다.

입력

첫째 줄에 구역의 개수 N이 주어진다. 둘째 줄에 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 주어진다. 인구는 공백으로 구분되어져 있다.

셋째 줄부터 N개의 줄에 각 구역과 인접한 구역의 정보가 주어진다. 각 정보의 첫 번째 정수는 그 구역과 인접한 구역의 수이고, 이후 인접한 구역의 번호가 주어진다. 모든 값은 정수로 구분되어져 있다.

구역 A가 구역 B와 인접하면 구역 B도 구역 A와 인접하다. 인접한 구역이 없을 수도 있다.

출력

첫째 줄에 백준시를 두 선거구로 나누었을 때, 두 선거구의 인구 차이의 최솟값을 출력한다. 두 선거구로 나눌 수 없는 경우에는 -1을 출력한다.

제한

• 2 ≤ N ≤ 10
• 1 ≤ 구역의 인구 수 ≤ 100

 

프로그래머스가 아니라 백준에서 풀어본 문제, 시간이 꽤 오래 걸렸던 문제였다.

 

N = int(input())
population = list(map(int, input().split()))
all_pop = sum(population)

zone = {key: [] for key in range(1, N+1)}

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

 

데이터를 입력 받는 부분,

N :  선거구의 수

population : 선거구별 인구수 (가장 앞에부터 1번)

all_pop : 모든 선거구의 인구수 총합

zone : 선거구의 그래프, 이때, 입력받을 데이터의 0번째 값은 간선의 갯수를 나타내는 데이터기 때문에 제외하고 입력한다.

 

from itertools import combinations

# N = int(input())
# population = list(map(int, input().split()))
# all_pop = sum(population)
# 
# zone = {key: [] for key in range(1, N+1)}
# 
# for i in range(1, N+1):
#     zone[i] = list(map(int, input().split()))[1:]

my_zone = []
another_zone = []

for i in range(1, N):
    for comb in combinations(range(1, N+1), i):
        comb = set(comb)
        my_zone.append(comb)
        another_zone.append(set(range(1, N+1)) - comb)

 

모든 선거구들의 조합을 구하기 위해서 combinations을 임포트 해준다.

그리고 선거구의 수 별로 모든 조합을 구한다. 단, 모든 선거구가 같은 구역에 속하는 경우는 없으므로 1개에서 N-1개 까지의 조합만 고려하면 된다.

한가지 구역을 구하고 그것을 my_zone이라는 리스트에 저장을 한 후, 그 구역에 속하지 않는 나머지 구역을 전부 another_zone이라는 리스트에 저장을 한다.

위의 방법을 통해서 모든 조합에 대해 순서쌍을 구할 수 있다.

# from itertools import combinations
# 
# N = int(input())
# population = list(map(int, input().split()))
# all_pop = sum(population)
# 
# zone = {key: [] for key in range(1, N+1)}
# 
# for i in range(1, N+1):
#     zone[i] = list(map(int, input().split()))[1:]
# 
# my_zone = []
# another_zone = []
# 
# for i in range(1, N):
#     for comb in combinations(range(1, N+1), i):
#         comb = set(comb)
#         my_zone.append(comb)
#         another_zone.append(set(range(1, N+1)) - comb)

explore = []
divided_zone = []

for m, a in zip(my_zone, another_zone):
    if m not in explore and a not in explore:
        explore.append(m)
        explore.append(a)
        if is_connect(m) and is_connect(a):
            divided_zone.append(list(m))

 

위에서 구한 구역들의 순서쌍을 기준으로 각 각 구역들 내부의 선거구(노드)들이 모두 연결되어 있는지 탐색을 수행한다.

탐색을 할 구역들은 explore라는 리스트에 저장을 해서 중복 탐색을 방지한다.

is_connect라는 함수를 통해서 각 구역들의 모든 노드들이 연결되었는지 탐색을 하고 모두 연결되어있는 경우 divided_zone에 둘중 한 구역만 추가한다. (두 선거구의 인구의 차이의 최소값을 구해야하는 문제기 때문에 둘중 한 선거구의 인구만 알고있으면 되기 때문이다.)

 

def is_connect(z):
    if len(z) == 1:
        return True
    z = list(z)
    connect = [z[0]]
    for constituency in connect:
        for node in zone[constituency]:
            if node in z and node not in connect:
                connect.append(node)
    return len(z) == len(connect)

 

입력받은 선거구 z를 기준으로 탐색을 한다.

z의 원소의 수가 1개인경우 항상 연결이 성립하기 때문에 즉시 True를 반환한다.

z의 가장 앞의 원소를 connect라는 리스트에 저장을 하고 connect의 원소의 수를 모두 탐색한다.

선거구 전체의 그래프인 zone의 현재 탐색중인 노드와 연결된 모든 노드들에 대해서 z에 속하고(같은 구역에 속한 원소들) connect에는 속하지 않는(중복탐색 방지) 값들은 connect에 추가한다.

각 선거구별로 연결된 모든 노드들을 구한 뒤 원소의 수가 입력받은  z의 원소의 수와 같은 경우, 모든 선거구가 연결되어있다는 의미이므로 True를 반환한다.

 

# from itertools import combinations
# 
# N = int(input())
# population = list(map(int, input().split()))
# all_pop = sum(population)
# 
# zone = {key: [] for key in range(1, N+1)}
# 
# for i in range(1, N+1):
#     zone[i] = list(map(int, input().split()))[1:]
# 
# my_zone = []
# another_zone = []
# 
# for i in range(1, N):
#     for comb in combinations(range(1, N+1), i):
#         comb = set(comb)
#         my_zone.append(comb)
#         another_zone.append(set(range(1, N+1)) - comb)
# 
# explore = []
# divided_zone = []
# 
# for m, a in zip(my_zone, another_zone):
#     if m not in explore and a not in explore:
#         explore.append(m)
#         explore.append(a)
#         if is_connect(m) and is_connect(a):
#             divided_zone.append(list(m))

if divided_zone:
    result = float('inf')
    for z in divided_zone:
        cur_pop = 0
        for my_pop in z:
            cur_pop += population[my_pop-1]
        result = min(result, abs(all_pop - cur_pop * 2))
else:
    result = -1

print(result)

 

이제 divided_zone에는 올바르게 분할된 선거구들의 조합이 담겨있게 된다.

divided_zone이 비어있을 경우, 선거구들을 올바르게 분할할 수 없기 때문에 -1을 출력한다.

divided_zone이 비어있지 않을 경우, divided_zone의 모든 원소(분할된 선거구의 조합)에 대해서 해당 구역에 속한 모든 선거구들의 인구수를 구한 뒤, 다른 선거구와의 차이를 구한다. 그리고 가장 낮은 값을 지속적으로 업데이트를 하고 가장 낮은 값을 출력하면 된다.

 

from itertools import combinations

def is_connect(z):
    if len(z) == 1:
        return True
    z = list(z)
    connect = [z[0]]
    for constituency in connect:
        for node in zone[constituency]:
            if node in z and node not in connect:
                connect.append(node)
    return len(z) == len(connect)

N = int(input())
population = list(map(int, input().split()))
all_pop = sum(population)

zone = {key: [] for key in range(1, N+1)}

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

my_zone = []
another_zone = []

for i in range(1, N):
    for comb in combinations(range(1, N+1), i):
        comb = set(comb)
        my_zone.append(comb)
        another_zone.append(set(range(1, N+1)) - comb)

explore = []
divided_zone = []

for m, a in zip(my_zone, another_zone):
    if m not in explore and a not in explore:
        explore.append(m)
        explore.append(a)
        if is_connect(m) and is_connect(a):
            divided_zone.append(list(m))

if divided_zone:
    result = float('inf')
    for z in divided_zone:
        cur_pop = 0
        for my_pop in z:
            cur_pop += population[my_pop-1]
        result = min(result, abs(all_pop - cur_pop * 2))
else:
    result = -1

print(result)