백준 문제 중 17779번, 구현, ‘게리맨더링2’

백준 문제 중 17779번

https://www.acmicpc.net/problem/17779

문제

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

재현시는 크기가 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. 다음 칸은 경계선이다. (x, y), (x+1, y-1), …, (x+d1, y-d1) (x, y), (x+1, y+1), …, (x+d2, y+d2) (x+d1, y-d1), (x+d1+1, y-d1+1), … (x+d1+d2, y-d1+d2) (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]를 의미한다.

출력

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

제한

• 5 ≤ N ≤ 20
• 1 ≤ A[r][c] ≤ 100

---

풀이

처음에 선거구끼리의 최댓값과 최솟값의 차이를 구하는 부분을 투포인터 처럼 최댓값 쪽의 영역을 줄이고 최솟값을 줄이는 식으로 접근 했었는데 주어지는 배열들이 랜덤함으로 이런식으로는 구현하기가 상당히 까다로웠다.

문제를 다시살펴보니 제한으로 주어진 조건이 N이 커봤자 20 이하 이므로, 단순히 모든 x, y, d1, d2의 경우를 살펴보는 식으로 접근을 했다.

import sys
from copy import deepcopy
from pprint import pprint

n = int(input())
sections = [list(map(int, input().split())) for _ in range(n)]
fairest = []

 # 5개의 구역의 각각의 값을 구할 함수
def calc_min(x, y, d1, d2):
    sub_sections = deepcopy(sections)

     # 각각의 구역의 합을 저장할 리스트 선언
    sum_of_sections = [0, 0, 0, 0, 0]
    
     # 1번 구역의 경계선들의 합을 더해 5번 구역의 합에 저장하고, 경계선은 0으로 바꿔줌
    for i in range(d1 + 1):
        sum_of_sections[4] += sub_sections[x+i][y-i]
        sub_sections[x+i][y-i] = 0

     # 2번 구역의 경계선들의 합을 더해 5번 구역의 합에 저장하고, 경계선은 0으로 바꿔줌
    for j in range(d2 + 1):
        sum_of_sections[4] += sub_sections[x+j][y+j]
        sub_sections[x+j][y+j] = 0

     # 3번 구역의 경계선들의 합을 더해 5번 구역의 합에 저장하고, 경계선은 0으로 바꿔줌 
    for j in range(d2 + 1):
        sum_of_sections[4] += sub_sections[x+d1+j][y-d1+j]
        sub_sections[x+d1+j][y-d1+j] = 0
    # 4번 구역의 경계선들의 합을 더해 5번 구역의 합에 저장하고, 경계선은 0으로 바꿔줌
    for i in range(d1 + 1):
        sum_of_sections[4] += sub_sections[x+d2+i][y+d2-i]
        sub_sections[x+d2+i][y+d2-i] = 0

     # 1번 구역에 해당하는 값들을 더하고 0으로 바꿔줌
    for i in range(x + d1):
        for j in range(y + 1):
            if sub_sections[i][j] == 0:
                break
            sum_of_sections[0] += sub_sections[i][j]
            sub_sections[i][j] = 0

     # 2번 구역에 해당하는 값들을 더하고 0으로 바꿔줌
    for i in range(x + d2 + 1):
        for j in range(n-1, y, -1):
            if sub_sections[i][j] == 0:
                break
            sum_of_sections[1] += sub_sections[i][j]
            sub_sections[i][j] = 0

     # 3번 구역에 해당하는 값들을 더하고 0으로 바꿔줌
    for i in range(x + d1, n):
        for j in range(y - d1 + d2):
            if sub_sections[i][j] == 0:
                break
            sum_of_sections[2] += sub_sections[i][j]
            sub_sections[i][j] = 0

     # 4번 구역에 해당하는 값들을 더하고 0으로 바꿔줌
    for i in range(x + d2 + 1, n):
        for j in range(n-1, y - d1 + d2 - 1, -1):
            if sub_sections[i][j] == 0:
                break
            sum_of_sections[3] += sub_sections[i][j]
            sub_sections[i][j] = 0

     # 남은 수들은 모두 5번 영역이므로 5번영역에 더해줌
    for i in range(n):
        for j in range(n):
            sum_of_sections[4] += sub_sections[i][j]

     # 1 ~ 5번 구역중 최댓값과 최솟값의 차를 return
    return max(sum_of_sections) - min(sum_of_sections)

    


def gerrymandering(x, y):

    min_x_y = sys.maxsize
     # 조건을 만족하는 모든 x, y, d1, d2 에 대해 반복
    d1 = 1  
    while 0 <= y - d1:
        d2 = 1
        while y + d2 < n:
            if x + d1 + d2 > n - 1:
                break
            min_x_y = min(min_x_y, calc_min(x,y,d1,d2))
            d2 += 1
        d1 += 1
    return min_x_y
        
 # d1, d2 의 최솟값인 d1, d2 ≥ 1, 1 이 가능한  x, y 에 대해 d1, d2를 조사함
for x in range(n-2):
    for y in range(1,n-2):
        fairest.append(gerrymandering(x, y))

print(min(fairest))

23

배운점

문제에서 주어지는 조건들이 1,1 부터 시작하는 인덱싱인데, 문제 풀이를 할때 그냥 파이썬의 인덱싱인 0, 0 부터 시작하는 인덱싱으로 구현하려니까 상당히 헷갈리고 실수가 많았었다.
1열모두와 1행을 모두 0으로 갖는 버퍼를 두어 1, 1 부터 인덱싱 하는 방법을 고려하자.