[파이썬/백준 17779] 게리맨더링 2

링크 www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

문제

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

재현시는 크기가 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. 다음 칸은 경계선이다.
   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

 

코드

def divide(x, y, d1, d2):
    edge = [[0 for _ in range(n+1)] for _ in range(n+1)]
    # (x, y), (x+1, y-1), ..., (x+d1, y-d1)
    # (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
    for i in range(0, d1+1):
        edge[x+i][y-i] = 5
        edge[x+d2+i][y+d2-i] = 5
    # (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)
    for i in range(0, d2+1):
        edge[x+i][y+i] = 5
        edge[x+d1+i][y-d1+i] = 5
    # 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
    city_1 = 0
    for r in range(1, x+d1):
        for c in range(1, y+1):
            if edge[r][c] == 5:
                break
            city_1 += city[r][c]
    # 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
    city_2 = 0
    for r in range(1, x+d2+1):
        for c in range(n, y, -1):
            if edge[r][c] == 5:
                break
            city_2 += city[r][c]
    # 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
    city_3 = 0
    for r in range(x+d1, n+1):
        for c in range(1, y-d1+d2):
            if edge[r][c] == 5:
                break
            city_3 += city[r][c]
    # 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N
    city_4 = 0
    for r in range(x+d2+1, n+1):
        for c in range(n, y-d1+d2-1, -1):
            if edge[r][c] == 5:
                break
            city_4 += city[r][c]
    # 5번 선거구
    city_5 = sum([sum(p) for p in city]) - (city_1+city_2+city_3+city_4)

    return max(city_1, city_2, city_3, city_4, city_5) - min(city_1, city_2, city_3, city_4, city_5)


n = int(input())
city = [[0 for _ in range(n)]] + [[0] + list(map(int, input().split())) for _ in range(n)]
answer = float('inf')

# 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
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 or 1 > y-d1 or y+d2 > n:
                    continue
                answer = min(answer, divide(x, y, d1, d2))
print(answer)