백준 17471. 게리맨더링(python)

17471. 게리맨더링

17471번: 게리맨더링

---

입력

• 첫째 줄에 구역의 개수 N이 주어진다.
• 둘째 줄에 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 주어진다.
• 셋째 줄부터 N개의 줄에 각구역과 인접한 구역의 정보가 주어진다.
• A가 B와 인접하면 B도 A와 인접하다.

---

문제 풀이

• 지역구가 정확히 둘로 나뉘었을 때, 두 지역구 인구차의 최솟값을 구해야한다.
• 또한 두 지역구로 나누지 못할 때는 -1을 출력하면 된다.

N = int(input())
popul = [*map(int, input().split())]
jun = sum(popul)
arr = [0]*(N+1)
check = [0]*(N+1)
minn = 21e10
flag = 0
for i in range(1, N+1):
    n, *arr[i] = [*map(int, input().split())]

• 입출력을 받는다.
• jun 은 전체 인구수를 나타내고, check 배열은 각 구역이 몇 번 지역구로 포함될지 표시하는 리스트이다.

for i in range(1<<N):
    cnt = 0         # 1번 지역구 개수
    start1 = 0      # 1번 지역구 탐색 시작할 번호 저장할 변수
    for j in range(N):
        if i & (1<<j):          # 지역구가 나눠지는 모든 경우의 수
            check[j+1] = 1      # 1번 지역구 표시
            start1 = j + 1
            cnt += 1
        else:
            check[j+1] = 2      # 2번 지역구 표시
            start2 = j + 1

• 두 지역구로 나뉠 수 있는 모든 경우를 비교해야하기에 비트 연산을 통해 모든 경우를 나타내었다.

    if  cnt == 0 or cnt == N:
        continue
    else:
        s1 = bfs(start1, cnt, 1, 0)     # 1번 지역구 모두 이어져 있는지 검사
        s2 = bfs(start2, N-cnt, 2, 0)   # 2번 지역구 모두 이어져 있는지 검사
        if s1:
            if s2:          # 두 지역구 모두 0 반환되지 않았으면
                flag = 1    # flag 킴
                minn = min(minn, abs(jun-2*s1)) # 최솟값과 인구 차이 비교하여 갱신

• 한 지역구로 모든 구역이 포함된다면, 검사할 필요가 없다.
• 그렇지 않은 경우에는 위에서 표시한 지역구들이 각각 모두 이어져 있는지 bfs를 통해 검사하였다.
• bfs 함수에서 반환 받은 값이 둘 다 0이 아니면, 두 구역으로 나뉠 수 있으므로, 기존의 최솟값과 구한 인구 차를 비교하여 갱신한다.
• bfs 함수의 구조는 다음과 같다.

def bfs(v, cnt, team, sum):     # team - 지역구(1 or 2), sum - 인구 합
    visited = [0]*(N+1)
    queue = deque()
    queue.append(v)
    visited[v] = 1
    cnt -= 1
    sum = popul[v-1]
    while queue:
        now = queue.popleft()
        for i in arr[now]:
            if visited[i] == 0 and check[i] == team:    # 방문하지 않았고 같은 지역구이면 방문
                visited[i] = 1
                queue.append(i)
                cnt -= 1
                sum += popul[i-1]
    if cnt != 0:    # 만약 방문 못한 곳 있으면 0 반환
        return 0
    else:           # 그렇지 않으면 인구 합 반환
        return sum

• bfs 알고리즘 뼈대에 같은 지역구인지 판별하고, 모든 지역구를 방문했는지 체크하는 코드를 추가하였다.
• 만약 모든 지역구가 이어져있지 않아, 방문하지 못한 구역이 있다면 0을 반환, 그렇지 않다면 인구의 합을 반환한다.

if flag == 1:           # flag 켜졌으면 
    print(f'{minn}')    # 최솟값 출력
else:                   
    print(-1)

• 만약 최솟값 갱신이 한 번이라도 됐다면, 두 구역으로 나뉠 수 있는 경우가 존재하는 것이므로 인구 차의 최솟값을 출력한다.
• 그렇지 않다면 -1을 출력한다.