백준 17779 게리맨더링 2 (파이썬)

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

17779번: 게리맨더링 2

1. 입력받은 지도에서 인구 총합을 구해놓는다

2. 기준점의 x축은 0부터 n-2, y축은 1부터 n-1까지 가능하다

   위의 범위안에서 divide 함수를 실행하여 모든 경우를 다 구해본다

3. d1과 d2를 1로 시작해서 d2를 하나씩 늘려간다.

   범위를 벗어나면 d1을 증가시키고 다시 d2를 1부터 늘려가면서 가능한 모든 d1, d2를 검증한다

4. 왼쪽, 오른쪽, 아래 꼭지점을 구하고 find_min 함수로 각 선거구의 인구수를 구한다

5. 각 선거구에서 5번 지역은 제외하고 인구수를 합한다

   5번 선거구 인구수는 처음에 구한 인구 총합에서 다른 선거구 인구수를 빼서 구한다

6. 최대 인구와 최소 인구를 뺀 값의 최소를 구하여 출력한다

import sys

input = sys.stdin.readline

def divide(x, y, d1, d2, ans):
    while True:
        while True:
            lx, ly, rx, ry = x + d1, y - d1, x + d2, y + d2
            if rx == n-1 or ry == n:
                break
            bx, by = x + d1 + d2, y - d1 + d2
            if bx >= n or by >= n or by < 0:
                break
            ans = min(ans, find_min(x, y, lx, ly, rx, ry, by))
            d2 += 1
        d1 += 1
        if x + d1 == n-1 or y - d1 == -1:
            break
        d2 = 1

    return ans

def find_min(x, y, lx, ly, rx, ry, by):
    cnt1, cnt2, cnt3, cnt4, d = 0, 0, 0, 0, 0
    for i in range(lx):
        for j in range(y+1):
            if [i, j] == [x + d, y - d]:
                d += 1
                break
            cnt1 += a[i][j]

    d = 1
    for i in range(rx+1):
        for j in range(n-1, y, -1):
            if [i, j] == [x + d, y + d]:
                d += 1
                break
            cnt2 += a[i][j]

    d = 0
    for i in range(lx, n):
        for j in range(by):
            if [i, j] == [lx + d, ly + d]:
                d += 1
                break
            cnt3 += a[i][j]

    d = 1
    for i in range(rx+1, n):
        for j in range(n-1, by-1, -1):
            if [i, j] == [rx + d, ry - d]:
                d += 1
                break
            cnt4 += a[i][j]

    cnt5 = nsum - cnt1 - cnt2 - cnt3 - cnt4
    max_cnt = max(cnt1, cnt2, cnt3, cnt4, cnt5)
    min_cnt = min(cnt1, cnt2, cnt3, cnt4, cnt5)
    return max_cnt - min_cnt

n = int(input())

a, nsum = [], 0
for _ in range(n):
    row = list(map(int, input().split()))
    nsum += sum(row)
    a.append(row)

ans = sys.maxsize
for i in range(n-2):
    for j in range(1, n-1):
        d1, d2 = 1, 1
        ans = divide(i, j, d1, d2, ans)
print(ans)