Baekjoon [17471] 게리맨더링 - python

문제 

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

17471번: 게리맨더링

 

문제 풀이

#  구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다.
#  선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다.
#  구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다.
#  중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.
import itertools
import collections
import sys
input = sys.stdin.readline

def bfs(same):
    start = same[0] # 조합된 노드 중 첫번째 노드로 start지점 생성
    # print(start)
    q = collections.deque([start]) # deque로 탐색 노드 값 저장
    visited = set([start])
    # print(visited)
    _sum = 0
    while q:
        v = q.popleft() # 처음 노드 값 추출
        _sum += node_number[v] # 해당 노드의 인구수 값 저장
        # print(linked_list[v])
        for u in linked_list[v]: # 탐색할 노드의 인접 노드 탐색
            if u not in visited and u in same: # 인접 노드가 방문하지 않은 노드이며 조합된 노드들로 구성된 경우,
                q.append(u) # q에 추가
                visited.add(u) # 방문한 노드로 체크
    return _sum, len(visited) # 탐색 한 노드들의 인구수 합, 노드 길이 리턴


n = int(input())
node_number = list(map(int,input().split()))
# print(node_number)
result = float('inf')
linked_list = [[] for _ in range(n)]

for i in range(n):
    near_node = list(map(int,input().split()))
    for j in range(1, near_node[0] + 1):
        linked_list[i].append(near_node[j] - 1)

    # linked list형태로 인접 노드 저장
# print(linked_list)
for i in range(1, n//2 + 1):
    combis = list(itertools.combinations(range(n), i)) # 주어진 노드로 조합 생성
    for combi in combis: # 조합 탐색
        # print(combi)
        sum1, v1 = bfs(combi) # 조합 된 노드 탐색 시작
        sum2, v2 = bfs([i for i in range(n) if i not in combi]) # 그외 조합되지 않은 노트 탐색 시작
        if v1 + v2 == n:  # 2번의 bfs를 통해 모든 노드가 방문되었는지 확인한다.
            result = min(result, abs(sum1 - sum2))

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

 

문제 접근

#  구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다.
#  선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다.
#  구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다.
#  중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

 

문제는 다음과 같다. 

1. 구역을 2개로 나눈다.

2. 구역은 모두 연결되어야 한다.

3. 인접한 구역을 탐색하여 연결된 노드들을 탐색한다.

4. 연결된 노드들의 인구 정보를 계산한다.

5. 노드를 전부 탐색하여 2개의 구역으로 나눠졌을 때 합한 인구정보의 차가 최소가 되게 만든다.

 

해당 방식에 대한 어려움이 생겨 타인의 코드를 참고했다.

[참고 코드]

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

 

코드의 진행 방식은 다음과 같다.

1. 인풋값들을 링크드 리스트를 통해 노드에 인접한 노드 번호를 저장한다.

 

2. 구역을 2개로 나누기 위해 조합을 사용한다. 이때 조합을 사용할 때 n//2를 하는 이유는 다음과 같다. 전체 n에서 특정 조합을 만들고 특정 조합을 제외한 차집합을 구할 때 나오는 경우의 수는 반대 조건일 때 해당 되기 때문에, 최대 n/2의 수로 조합을 만드는 것이다.

ex) 6개의 덩어리에서 2,4로 나누는 것과 4,2 로 나누는 것은 동일하다는 의미.

즉 최대 3,3까지 나오는 경우의수가 제일 많은 경우의 수!!

 

3. 조합을 나눴으면 조합의 시작 노드를 바탕으로 BFS탐색을 진행한다. 이때 사용되는 변수들은 인구정보를 담고 있는 리스트 변수와 링크드 리스트로 구현되어있는 리스트를 사용한다.

 

4. 조합으로 만들어진 경우의 수에 있는 노드들이 탐색하지 않는 노드이면서 시작노드와 인접한 노드일 경우 인구정보를 계산하며 탐색을 시작.

 

5. 계산이 될수록 result변수를 통해 최소값 비교를 통해 값을 추출한다.

 

6. 값 도출

 

위 방식으로 알고리즘이 작동을 하였다. 처음에 조합 방식 자체를 생각하지 못해 구역을 나누는데 있어 어려움을 겪었다. 보다 나은 알고리즘 풀이를 위해 다양한 방식으로 접근해보는 사고력을 기르자!!