백준 ) 게리맨더링

문제) 게리맨더링

 

문제에서 요구하는 사항은 2개의 선거 구역은 구분 지어 인구수 차가 최대한 적을 때의 값을 찾는 것이다

이때 나누어 진 구역은 서로 연결 되어 있어야 하며 구역은 최소 1개의 구역이 되어 한다

 

위의 조건은 보고 처음 풀이 접근 하기가 조금 어려웠다.

 

이유는 처음 입력을 이해하기가 조금 어려웠다.

 

이제는 해당 입력에 대하여 설명을 할 수 있을 정도가 되었으나 처음 풀이 할때에는 2번째 줄까지만 이해하고 이후 줄을 이해하기까지 조금 시간이 걸렸다.

 

결국은 첫번째 줄은 구역의 수이며 두번째 줄은 각 구역의 인구수를 순차적으로 주어 졌다

그다음 줄은 각 구역의 연결된 구역의 수와 구역의 이름을 주어 진다

 

이를 통하여 기본 적인 코딩을 진행 하면 아래와 같은 코딩이 나온다

import sys
N = int(sys.stdin.readline().strip())
peple_lst = list(map(int, sys.stdin.readline().split())
graph = {}
for i in rnage(1, N + 1):
	info = list(map(int, sys.stdin.readline().split())
	graph[i] = info[1:]

 

이렇게 기초 코딩 을 한 뒤 이제는 각 구역을 조합한 뒤 조합 된 내용을 기준으로 연결 여부 를 확인 하면 된다

그런 뒤 연결 되었다면 두 구역의 인구수의 합 구한 뒤 그 차이를 비교하면 된다

 

파이썬에서 조합은 직접 구현을 하지 않아도 itertools 패키지를 통하여 사용 할 수있다

 

이번 풀이 때에는 조금 어려웠기도 하고 저번 스쿼드 탐방 때 튜터님이 코딩하는 방식이 기억이 남아 내가 무엇을 구현해야 되는 지 글로 적은 뒤 그 글로 적은 부분을 구현을 하였다.

 

# """
# 1. 최소 한개 이상의 구역이 필요
#     1.1 [1], [2, 3, 4, 5, 6, 7] ....
#     1.2 [1, 2], [3, 4, 5, 6, 7] ....
#     1.3 [1, 2 ,3], [4, 5, 6, 7] ....
# --------------------------------------
# 2. 한개 면 다른 남은 부분연 연결 확인
# 3. 한개 이상 이면 연결 되는지 검증
# 4. 최소 값을 찾기에 모든 경우의 수를 찾아 최소 값 찾기
#     4.1 0 이면 바로 반환
# """

 

위의 글 처럼 일단 조합을 먼저 구하고 이후 나누어진 구역들의 수를 체크 하여 1개 이상이면 연결 여부를 확인 하는 코드를 추가하면 된다

 

1번의 조합을 보면 알 듯이 전체 크기N의 (N/2) + 1 만큼만 조회하면 된다

이후 dp를 사용하여 풀이를 진행하기도 했는데 dp를 이용 할 경우 모든 구역이 연결 되어 있는지 확인 불가능 하여 bfs를 통하여 해당 문제를 다시 풀었다.

• 예시( 1-2, 3-4, 5-6) 이렇게 3개 구역으로 나누어 졌을때 조합을 하면 (1-2, 3-4), (5-6) 이 되고 내가 작성한 dp의 경우 1-2 연결 확인 3-4 연결 확인 되어 통과가 된다.
• 이를 해결 하기 위해서는 제일 앞에 있는 1로 통하여 모두 연결 되는지 확인 하는 방식이 필요하다.
• 1-2-3이나 1-2-4 가 되는지를 확인 해야 하는데 dp보다는 bfs나 dfs 방식으로 푸는게 좀 더 쉽게 코딩이 가능하다

 

정답 코드

import sys
from collections import deque
from itertools import combinations
N = int(sys.stdin.readline().strip())
p_count = list(map(int, sys.stdin.readline().split()))
graph = {}
for i in range(1, N + 1):
    lst = list(map(int, sys.stdin.readline().split()))
    graph[i] = lst[1:]
    
num_list = list(graph.keys())


def bfs(groups, tree):
    peple_sum = 0
    visited = {idx: False for idx in groups}
    dq = deque([groups[0]])
    while dq:
        node = dq.popleft()
        for idx in tree[node]:
            if idx in visited and not visited[idx]:
                visited[idx] = True
                dq.append(idx)

    if False in visited.values():
        peple_sum = -1
    else:
        for idx in groups:
            peple_sum += p_count[idx - 1]

    return peple_sum


min_v = sum(p_count)
for k in range(1, (N // 2) + 1):
    combi = combinations(num_list, k)
    for j in list(combi):
        A = list(j)
        if k > 1:
            check1 = bfs(A, graph)
        else:
            check1 = p_count[A[0] - 1]

        if check1 < 0:
            continue

        B = list(set(num_list) - set(j))
        if len(B) > 1:
            check2 = bfs(B, graph)
        else:
            check2 = p_count[B[0] - 1]
        if check2 < 0:
            continue

        min_v = min(min_v, abs(check2 - check1))
        if min_v == 0:
            break

    if min_v == 0:
        break

if min_v == sum(p_count):
    min_v = -1
sys.stdout.write(f'{min_v}')