(Python) 백준 17779번 : 게리맨더링2

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

17779번: 게리맨더링 2

---

백준 / 17779번 / 게리맨더링 2¶

---

In [8]:

# for 블로그 포스팅
from IPython.core.display import display, HTML 
display(HTML("<style>.container {width:90% !important;}</style>"))

In [1]:

N = int(input())

dt_map = []
for i in range(N):
    dt_map.append([int(j) for j in input().split()])

6
1 2 3 4 1 6
7 8 9 1 4 2
2 3 4 1 1 3
6 6 6 6 9 4
9 1 9 1 9 5
1 1 1 1 9 9

In [2]:

## 1번 구역 합 구하기 
def sum_1D(graph, x, y, d1, d2):
    sum_1 = 0
    for i in range(0, x+d1):
        for j in range(0, y+1):
            sum_1 = sum_1 + graph[i][j]
    #5구역에 해당하는 곳 제외
    t = -1
    for i in range(x, x+d1):
        t = t+1
        for j in range(y-t,y+1):
            sum_1 = sum_1 - graph[i][j]
    return sum_1

In [3]:

## 2번 구역 합 구하기
def sum_2D(graph, x, y, d1, d2):
    sum_2 = 0
    for i in range(0, x+d2+1):
        for j in range(y+1, N):
            sum_2 = sum_2 + graph[i][j]
    #5구역에 해당하는 곳 제외
    t = 0
    for i in range(x+1, x+d2+1):
        t = t+1
        for j in range(y+1, y+1+t):
            sum_2 = sum_2 - graph[i][j]
    return sum_2

In [4]:

## 3번 구역 합 구하기
def sum_3D(graph, x, y, d1, d2):
    sum_3 = 0
    for i in range(x+d1, N):
        for j in range(0, y-d1+d2):
            sum_3 = sum_3 + graph[i][j]
    #5구역 제외
    t = -1
    for i in range(x+d1, x+d1+d2+1):
        t = t+1
        for j in range(y-d1+t, y-d1+d2):
            sum_3 = sum_3 - graph[i][j]
    return sum_3

In [5]:

## 4번 구역 합 구하기
def sum_4D(graph, x, y, d1, d2):
    sum_4 = 0
    for i in range(x+d2+1,N):
        for j in range(y-d1+d2, N):
            sum_4 = sum_4 + graph[i][j]
    #5구역 제외
    t = -1
    for i in range(x+d2+1, x+d2+d1+1):
        t = t+1
        for j in range(y-d1+d2, y+d2-t):
            sum_4 = sum_4 - graph[i][j]
    return sum_4

In [6]:

# 전체 구역 합을 구한다.(나중에 5구역 구하기위해서)
# 5구역 = 전체 구역 - (1구역 + 2구역 + 3구역 + 4구역)
total_sum = 0
for i in range(N):
    total_sum = total_sum + sum(dt_map[i])

In [7]:

minvalue = float('inf') # 최솟값 = 인구가 가장 많은 선거구 - 가장 적은 선거구
for x in range(0,N-2):
    for y in range(1, N-1):
        for d1 in range(1, y+1):
            for d2 in range(1, N-y):
                try:
                    district = []
                    district.append(sum_1D(dt_map, x, y, d1, d2)) #1번구역
                    district.append(sum_2D(dt_map, x, y, d1, d2)) #2번구역
                    district.append(sum_3D(dt_map, x, y, d1, d2)) #3번구역
                    district.append(sum_4D(dt_map, x, y, d1, d2)) #4번구역
                    district.append(total_sum - sum(district)) #5번구역
                    district.sort() #값이 5개밖에 안되므로 정렬해주자
                    if minvalue > district[-1]-district[0]:
                        minvalue = district[-1]-district[0]
                except: #에러 발생(아마도 indexerror일 가능성이 큼)
                    break
print(minvalue)

18