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

링크

백준 17471 게리맨더링

풀기전에 어떻게 풀어야 할지 순서를 먼저 정해서 풀었다.
1. 선거구를 나눈다
2. 선거구가 유효한지 검사한다
3. 유효하면 인구수를 계산한다

순서를 나누니 풀 방법이 보였다.

1. 선거구를 나눈다

   powerset을 백트래킹을 활용해 구현
   하나의 선거구만 구한 후 전체 선거구집합에서 차집합해 다른 선거구 구함

2. 선거구가 유효한지 검사

   dfs활용해 방문 가능한지 검사
   이때, 선거구가 도시 1개로 이루어져 있으면 무조건 유효

3. 인구수 계산

   처음에 인구수를 받을 떄 인덱스를 활용하기 쉽게 0번 인덱스는 사용하지 않게 만듬

지금 코드는 powerset을 만들 때 중복이 생기는데 해당 부분을 개선하기 위해 고민해봐야 겠다.

정답 코드

import sys; input = sys.stdin.readline

def make_area(idx, powerset):
    global min_dif
    if idx == N:
        if 0 < len(powerset) < N:
            area1 = powerset
            area2 = list(set(cities) - set(area1))
            if is_linked(area1) and is_linked(area2):
                dif = abs(get_population(area1) - get_population(area2))
                if dif < min_dif:
                    min_dif = dif
    else:
        make_area(idx + 1, powerset)
        make_area(idx + 1, powerset + [cities[idx]])

def is_linked(area): #dfs
    if len(area) == 1:
        return True
    stack = [area[0]]
    visited = [0] * (N + 1)
    visited[stack[0]] = 1
    cnt = 1
    while stack:
        v = stack.pop()
        for ad in adjacency[v]:
            if visited[ad] == 0 and ad in area: #방문한적 없고 방문해야할 도시이면 방문
                visited[ad] = 1
                stack.append(ad)
                cnt += 1
                if cnt == len(area):
                    return True
    return False

def get_population(area):
    total = 0
    for city in area:
        total += population[city]
    return total

N = int(input())
population = [0] + list(map(int, input().split()))
adjacency = {} #인접리스트 저장
cities = []
min_dif = 987654321
for i in range(1, N + 1):
    cities.append(i)
    adjacency[i] = list(map(int, input().split()))[1:] #갯수 빼고 리스트로 받아서

make_area(0, [])
print(min_dif if min_dif != 987654321 else -1)
#구역을 2개로 나눔
#구역이 연결되어있는지 체크
#인구수 계산

알게된 것👨‍💻

• 백트래킹 + dfs