8/1 Coding Test

✅ BOJ

🎈 17779 게리맨더링 2

주어진 시의 이름은 재현시로 NXN의 격자로 나타낼 수 있다. r행 c열의 구역은 (r,c)로 나타낼 수 있고 주어진 시를 5개의 선거구로 나눌 수 있어야 하며 각 구역은 다섯 선거구 중 하나에 포함되어야 한다.

선거구를 나누는 방법은 다음과 같다.
1. 기준점 (X, Y)와 경계의 길이 (d1, d2)를 정한다. (d1, d2 >=1, 1<=x<x+d1+d2<=N, 1<=y-d1<y<y+d2<=N)
2. 경계선이 주어진다. (경계선의 범위는 +- d1, d2로 총 4개)
3. 경계선과 경계선 내 포함된 곳은 5번 선거구

• 입력값 : 첫줄에는 크기 n, 둘째 줄부터 n줄까지 n개의 정수가 주어짐.
• 출력값 : 첫줄에 인구가 가장많은 선거구와 가장 적은 선거구의 인구 차이 최솟값 출력

import sys
input = sys.stdin.readline

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

total_sum = 0
for i in range(1, n+1):
    total_sum += sum(graph[i])

def boundary(x, y, d1, d2):
    tmp = [[0]*(n+1) for _ in range(n+1)]
    tmp[x][y] = 5
    for i in range(1, d1+1):
        tmp[x+i][y-i] = 5
    for i in range(1, d1+1):
        tmp[x+d2+i][y+d2-i] = 5
    for i in range(1, d2+1):
        tmp[x+i][y+i] = 5
    for i in range(1, d2+1):
        tmp[x+d1+i][y-d1+i] = 5
    # 선거구 5개
    people = [0] * 5

    # 1번 선거구
    for i in range(1, x+d1):
        for j in range(1, y+1):
            if tmp[i][j] == 5:
                break
            else:
                people[0] += graph[i][j]
    # 2번
    for i in range(1, x+d2+1):
        for j in range(n, y, -1):
            if tmp[i][j] == 5:
                break
            else:
                people[1] += graph[i][j]
    # 3번
    for i in range(x+d1, n+1):
        for j in range(1, y-d1+d2):
            if tmp[i][j] == 5:
                break
            else:
                people[2] += graph[i][j]
    # 4번
    for i in range(x+d2+1, n+1):
        for j in range(n, y-d1+d2-1, -1):
            if tmp[i][j] == 5:
                break
            else:
                people[3] += graph[i][j]
    # 5번
    people[4] += total_sum - sum(people)
    return max(people) - min(people)

answer = 1e9
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 x+d1+d2 > n:
                    continue
                if y-d1 < 1:
                    continue
                if y+d2 > n:
                    continue
                answer = min(answer, boundary(x,y,d1,d2))
print(answer)