[백준] 게리 멘더링2

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

17779번: 게리맨더링 2

정말 정말 귀찮은 2차원 배열 시뮬레이션, 브루트포스 문제입니다. 모든 x, y, d1, d2 조합에 대해 각각의 구역의 인구수를 계산해주면 됩니다. 가장 어려웠던 부분은 구역을 나누는 부분인데 저는 다음과 같이 해결하였습니다.

 

1. 먼저, 5번 구역에 대해 처리를 먼저 해줍니다. 5번 구역에 대한 경계선을 미리 체크해주고 5번 구역의 경계 안에 있는 부분들도 체크해줍니다. 최상단 행과 최하단 행에는 구역이 무조건 한칸만 존재하게 되므로 두 행들을 제외하고 나머지 행들에 대해서 탐색하면서 5를 처음 만났으면 경계안으로 진입 두번째 5를 만났으면 경계 밖으로 나간 것으로 flag를 통해 체크해주고 경계 안에 있을 때에만 체크해줍니다.

 

2. 그 다음 나머지 구역들에 대해 처리해주는데 이것도 문제의 공식에 따라 각각의 구역이 존재할 수 있는 행과 열의 범위를 탐색하면서 1, 3구역은 5를 만난 경우에는 5번 구역으로 넘어간 경우이고 2, 4 구역은 5번 구역을 만나지 않는 구간부터 해당 구역이 시작도록 계산해주면 됩니다.

 

 

import sys

# sys.stdin = open("input.txt", "r")

input = sys.stdin.readline

n = int(input())

board = [[0]* (n + 1)] + [
    [0] + list(map(int, input().split()))
    for _ in range(n)
]

ans = sys.maxsize

# 경계가 가능한 것인지
def check(d1, d2, x, y):
    return 1 <= x < x + d1 + d2 and x + d1 + d2 <= n and 1 <= y - d1 < y and y < y + d2 <= n

def markSectorFive(d1, d2, x, y, temp):
    cnt = 0

    for i in range(d1 + 1):
        temp[x + i][y - i] = 5
        temp[x + d2 + i][y + d2 - i] = 5

    for i in range(d2 + 1):
        temp[x + i][y + i] = 5
        temp[x + d1 + i][y - d1 + i] = 5

    cnt += board[x][y] + board[x + d1 + d2][y + d2 - d1]

    for i in range(x + 1, x + d1 + d2):
        flag = False
        for j in range(1, n + 1):
            # 경계인 구간들
            if temp[i][j] == 5:
                flag = not flag
                cnt += board[i][j]
            else:
                if flag:
                    temp[i][j] = 5
                    cnt += board[i][j]

    return cnt


def getMinSector(d1, d2, x, y):
    global ans

    temp = [
        [0] * (n + 1)
        for _ in range(n + 1)
    ]

    sectors = [0] * 6

    sectors[5] = markSectorFive(d1, d2, x, y, temp)
    # 1구역
    for i in range(1, x + d1):
        for j in range(1, y + 1):
            if temp[i][j] == 5:
                break
            sectors[1] += board[i][j]

    # 2구역
    for i in range(1, x + d2 + 1):
        for j in range(y + 1, n + 1):
            if temp[i][j] == 5:
                continue
            sectors[2] += board[i][j]

    # 3구역
    for i in range(x + d1, n + 1):
        for j in range(1, y - d1 + d2):
            if temp[i][j] == 5:
                break
            sectors[3] += board[i][j]

    # 4구역
    for i in range(x + d2 + 1, n + 1):
        for j in range(y - d1 + d2, n + 1):
            if temp[i][j] == 5:
                continue
            sectors[4] += board[i][j]

    max_po = max(sectors[1:])
    min_po = min(sectors[1:])

    if min_po == 0:
        return

    ans = min(ans, max_po - min_po)

for x in range(1, n + 1):
    for y in range(1, n + 1):
        for d1 in range(1, n + 1):
            for d2 in range(1, n + 1):
                if not check(d1, d2, x, y):
                    continue

                getMinSector(d1, d2, x, y)

print(ans)