백준: 17779 게리멘더링 2

문제

17779번: 게리맨더링 2

 

문제 풀이

 문제를 접하고 나서, 이게 무슨 말이지?😅 하며, 문제를 여러 번 읽어보았다. 하나의 구역(r, c)을 기준으로 `r, c, d1, d2`에 따라 5번 선거구의 크기가 달라지게 된다. 적절히 경계를 조정하여, 선거구마다 최대한 공평하게 인원이 나누어지도록 해야 하는 문제이다.

 

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

 

 위와 같이 문제에 주어진 조건에 따라, 경계 구역을 표기하기, 경계 구역의 나머지 영역을 1번, 2번, 3번, 4번 선거구로 선택한 후 최대 최소 값의 차를 계산해주면 된다. 즉, 위의 그림과 같이 하나의 지점 (r, c)를 선택한 후, 경계 경계 구역에 따라 5번 구역을 설정하고, 그 외의 나머지 영역의 값을 구하면 된다.

 

코드

from sys import stdin, maxsize

FIRST, SECOND, THIRD, FOURTH = 0, 1, 2, 3


def calculate(row, col, d1, d2):
    global total, answer
    zone = [0] * 4
    # 인덱스에 맞게 1씩 추가
    temp = [[0] * (N + 1) for _ in range(N + 1)]
    temp[row][col] = 5
    # d1 = 2 d2 = 2
    for i in range(1, d1 + 1):
        # 1번 경계 : (x, y), (x+1, y-1), ..., (x+d1, y-d1)
        temp[row + i][col - i] = 5
        # 4번 경계 : (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
        temp[row + d2 + i][col + d2 - i] = 5

    for i in range(1, d2 + 1):
        # 2번 경계 : (x, y), (x+1, y+1), ..., (x+d2, y+d2)
        temp[row + i][col + i] = 5
        # 3번 경계 : (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
        temp[row + d1 + i][col - d1 + i] = 5

    # 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
    for r in range(1, row + d1):
        for c in range(1, col + 1):
            if temp[r][c] == 5:
                break
            zone[FIRST] += board[r][c]

    # 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
    for r in range(1, row + d2 + 1):
        for c in range(N, col, -1):
            if temp[r][c] == 5:
                break
            zone[SECOND] += board[r][c]

    # 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
    for r in range(row + d1, N + 1):
        for c in range(1, col - d1 + d2):
            if temp[r][c] == 5:
                break
            zone[THIRD] += board[r][c]

    # 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N
    for r in range(row + d2 + 1, N + 1):
        for c in range(N, col - d1 + d2 - 1, -1):
            if temp[r][c] == 5:
                break
            zone[FOURTH] += board[r][c]

    fifth = total - sum(zone)

    return max(max(zone), fifth) - min(min(zone), fifth)


if __name__ == '__main__':
    N = int(input())
    board = [[]]

    for _ in range(N):
        # 인덱스에 맞게 1씩 추가
        board.append([0] + list(map(int, stdin.readline().split())))

    total = sum(sum(board, []))

    answer = maxsize

    for r in range(1, N + 1):
        for c in range(1, N + 1):
            for d1 in range(1, N + 1):
                for d2 in range(1, N + 1):
                    if r + d1 + d2 > N:
                        continue
                    if 1 > c - d1:
                        continue
                    if c + d2 > N:
                        continue
                    answer = min(answer, calculate(r, c, d1, d2))

    print(answer)