[백준/python] 17779번 : 게리맨더링 2

문제

재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

선거구를 나누는 방법은 다음과 같다.

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
2. 다음 칸은 경계선이다.
   1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
   2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
   3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
   4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.
   • 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
   • 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
   • 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
   • 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

아래는 크기가 7×7인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.

구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

 

입력

첫째 줄에 재현시의 크기 N이 주어진다.

둘째 줄부터 N개의 줄에 N개의 정수가 주어진다. r행 c열의 정수는 A[r][c]를 의미한다.

 

출력

첫째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력한다.

 

정답

import sys
input = sys.stdin.readline

N = int(input())
area = []
for _ in range(N):
    area.append(list(map(int, input().split())))

answer = 100*20*20  # 인구 차이의 최대값으로 리셋

# 기준점 (x, y) : 0 <= x < N-2, 1 <= y < N-1
for x in range(0, N-2):
    for y in range(1, N-1):
        
        # 경계의 길이 d1, d2 : 1 <= d1 <= y, 1 <= d2 <= N-y
        for d1 in range(1, y+1):
            for d2 in range(1, N-y+1):                
                if 0 <= y-d1 and y+d2 < N and x+d1+d2 < N:  # 인덱스 체크

                    cnt = [0, 0, 0, 0, 0]   # 0 ~ 4 구역 인구수 0으로 리셋
                    
                    # 확인할 구역 (r, c)
                    for r in range(N):
                        for c in range(N):
                            population = area[r][c]
                            
                            if r < x+d1 and c <= y:         # 0구역
                                if r+c >= x+y:
                                    cnt[4] += population
                                else:
                                    cnt[0] += population
                            
                            elif r <= x+d2 and y < c:       # 1구역
                                if r-c >= x-y:
                                    cnt[4] += population
                                else:
                                    cnt[1] += population
                            
                            elif x+d1 <= r and c < y-d1+d2: # 2구역
                                if r-c <= x-y+(2*d1):
                                    cnt[4] += population
                                else:
                                    cnt[2] += population
                            
                            elif x+d2 < r and y-d1+d2 <= c: # 3구역
                                if r+c <= x+y+(2*d2):
                                    cnt[4] += population
                                else:
                                    cnt[3] += population
                            
                            else:
                                cnt[4] += population
                    
                    answer = min(answer, max(cnt)-min(cnt))
                
                else:   # 마름모가 area를 벗어나는 경우
                    break

print(answer)

---

인덱스 편의를 위해 구역은 (0,0)에서 시작하고 1~5번 선거구는 0~4번 선거구로 설명하겠다.

 

우선 문제를 이해하기 위해 아래의 그림을 그려보았다.

가장 위에 있는 꼭지점을 기준점 (x, y)로 설정하고 경계의 길이 d1, d2일 때의 상황을 정리하면

위 그림과 같고 좌표의 범위를 한눈에 파악하기 쉽다.

 

answer = 100*20*20  # 인구 차이의 최대값으로 리셋

# 기준점 (x, y) : 0 <= x < N-2, 1 <= y < N-1
for x in range(0, N-2):
    for y in range(1, N-1):
        
        # 경계의 길이 d1, d2 : 1 <= d1 <= y, 1 <= d2 <= N-y
        for d1 in range(1, y+1):
            for d2 in range(1, N-y+1):                
                if 0 <= y-d1 and y+d2 < N and x+d1+d2 < N:  # 인덱스 체크

                    cnt = [0, 0, 0, 0, 0]   # 0 ~ 4 구역 인구수 0으로 리셋

 

각 구역의 최대 인구는 100이고 크기의 최대는 20*20이므로

인구 차이의 최대값은 100*20*20이며 answer를 인구 차이의 최대값으로 초기화한다.

 

가능한 모든 기준점에서 경계의 길이를 늘려가며 가능한 모든 경우의 수를 탐색한다.

경계 d1, d2는 최소 1 이상이기 때문에 

기준점 x는 0 <= x < N-2. 기준점 y는 1 <= y < N-1 의 범위를 갖는다.

 

문제에서 1 ≤ y-d1 < y < y+d2 ≤ N 이라 설명하므로 계산해보면

경계 d1은 1 <= d1 <= y, 경계 d2는 1 <= d2 <= N-y 의 범위를 갖는다.

이해가 안된다면 위 그림을 참고하면 이해하기 쉽다.

 

위 그림에서 파악한 좌표의 범위를 토대로 인덱스를 체크해준다.

만약 인덱스를 벗어났다면 더이상 경계를 늘릴 필요가 없으므로 break 한다.

 

cnt에는 각 구역의 인구수의 합을 저장할 것이므로 0으로 초기화해준다.

 

 

이제 모든 좌표를 돌며 어느 구역에 해당하는지 확인한다.

아래 그림은 각 구역의 좌표가 어떤 규칙이 있는지 파악하기 위해 그려본 그림이다.

파란 선은 각 선거구의 경계를 기준으로 나눈 선이다.

각 선거구 안에서 4번 선거구에 해당하는 구역 (r, c)는 보라색 글씨와 같은 규칙을 갖는다.

보라색 글씨의 규칙은 파란 동그라미 좌표 중 하나를 기준으로 작성되었다.

 

(r, c)가 네 구역 중 어디에 있는지 확인하고 

보라색 글씨와 같은 규칙을 기반으로 4 선거구인지 체크하여

해당 선거구 인덱스의 cnt 값에 (r, c) 구역의 값을 더해준다.

 

모든 선거구의 계산이 끝났으면

cnt의 최대값과 최소값의 차와 answer을 비교하여 더 작은 값을 answer에 저장한다.