[백준 알고리즘] 17471. 게리맨더링

 

💻 문제 풀이 방법

 

1. 가능한 경우의 수(조합) 구하기 (재귀 + 백트래킹 사용)

 

2. 1의 정보를 바탕으로 그룹을 나누고

 

3. 나눈 그룹 각각 DFS로 방문할 수 있는지 체크, 방문하지 못하는 노드가 있을 경우 제외

 

 

 

 

 

처음에는 인접정보를 판단하면서 경우의 수를 구하기 위해, 그래프를 사용하며 방문표시를 했는데,

 

경우의 수에서 제외되는 경우가 있어 정답을 구할 수 없었다.

 

경우의 수는 역시 완전 탐색을 하는 게 확실하다...

 

 

 

아래 주소는 문제 풀면서 참고했던 반례들인데 유용했다!

https://www.acmicpc.net/board/view/54133 반례들

 

 

# DFS
def check_areas(check):
    for i in range(1, N+1):
        if check[i] == 0:
            start = i
            break

    stack = [start]
    while stack:
        u = stack.pop()
        if check[u]: continue
        check[u] = 1
        for v in G[u]:
            stack.append(v)
    for i in check[1:]:
        if i == 0:
            return False
    return True


# 두개의 구역 나누기
def make_two_areas(lst):
    area1_visited = lst[:]
    area2_visited = [int(not i) for i in area1_visited] # 다른 선거지역
    if not check_areas(area1_visited):
        return False
    if not check_areas(area2_visited):
        return False
    return True


# 조합 백트래킹
def divide_area(idx, population):
    global ans
    if population > total // 2 : return
    if idx == N+1:
        diff = abs(total - population * 2)
        if diff < ans and make_two_areas(visited):
            ans = diff
        return
    visited[idx] = 1
    divide_area(idx + 1, population+arr[idx])
    visited[idx] = 0
    divide_area(idx + 1, population)
    return


# 선거구 나누기
# 두 구역의 인구 최솟값 구하기,  안되는 경우 -1 출력
# 구역 나눌 때 꼭 인접해야 함.

N = int(input()) # 구역의 개수
arr = [0] + list(map(int, input().split())) # 구역의 인구
G = [[] for _ in range(N+1)]
visited = [0] * (N+1)
for i in range(1, N+1):
    adj_area = list(map(int, input().split()))
    for adj in adj_area[1:]:
        G[i].append(adj)
total = sum(arr)
ans = total

divide_area(1, 0)
if total == ans:
    print(-1)
else:
    print(ans)