[Python][백준] 17779번 게리맨더링 2

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

공부 날짜 : 2022.09.26
정답 참조여부 : X

주어진 조건에 맞춰 구역을 분리하고 각 구역에서 인구수의 최대 최소의 차가 최소인 값을 구하는 문제이다.

---

x,y,d1,d2의 값에따라 구역이 분리가 되므로 4개의 for문으로 각 조합을 구해주었다.

4개의 값이 결정되고 조건에 따라 구역을 분리해주는데 기존에 사각형모양이 아닌 대각선 모양에서는 생각만큼 쉽게 분리가 되지 않았다.

예시로 주어지는 모양을 살펴보며 5구역을 기준으로 상 하 좌 우로 구분하고 좌,우의 경우 다시 x+d1의 상하, x+d2의 상하로 구분하여 각각의 구역을 나누어 주었다.

그 후 각 구역의 인구수를 담는 리스트를 선언하고 각 구역에서 자신의 구역에 맞게 인구수를 더해준뒤 최대최소의 차이를 최소가 되게 갱신해주면 정답이 나온다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())

people_graph = []

for _ in range(n):
    people_graph.append(list(map(int, input().split())))
    
result = int(10e9)

#x,y,d1,d2를 결정
for x in range(1, n+1):
    for y in range(1, n+1):
        for d1 in range(1, y):
            for d2 in range(1, n-y+1):
                #d1과 d2가 조건에 안맞으면 다음반복
                if (1 <= x+d1+d2 <= n) == False:
                    continue
                    
                #결정된 x,y,d1,d2에 따라 각 선거구로 인구 분리
                people_range = [0]*5
                for r in range(1,n+1):
                    for c in range(1,n+1):
                        
                        # 5선거구 사각형 범위 위
                        if 1 <= r < x:
                            # 1선거구
                            if 1 <= c <= y:
                                people_range[0] += people_graph[r-1][c-1]
                            # 2선거구
                            elif y < c <= n:
                                people_range[1] += people_graph[r-1][c-1]
                                
                        # 5선거구 사각형 범위 내   
                        elif x <= r <= x+d1+d2:
                            #5선거구 범위 좌
                            if c < y - d1 + abs(x+d1-r):
                                # 1선거구
                                if 1 <= r < x+d1:
                                    people_range[0] += people_graph[r-1][c-1]
                                # 3선거구
                                elif x+d1 <= r <= n:
                                    people_range[2] += people_graph[r-1][c-1]
                                
                            # 5선거구
                            if y-d1+abs(x+d1-r) <= c <= y+d2-abs(x+d2-r):
                                people_range[4] += people_graph[r-1][c-1]
                                
                            #5선거구 범위 우
                            elif c > y+d2 - abs(x+d2-r):
                                # 2선거구
                                if 1 <= r <= x+d2:
                                    people_range[1] += people_graph[r-1][c-1]
                                # 4선거구    
                                elif x+d2 < r <= n:
                                    people_range[3] += people_graph[r-1][c-1]
                                
                        # 5선거구 사각형 범위 아래
                        elif x+d1+d2 < r <= n:
                            # 3선거구
                            if 0 < c < y-d1+d2:
                                people_range[2] += people_graph[r-1][c-1]
                            # 4선거구
                            elif y-d1+d2 <= c <= n:
                                people_range[3] += people_graph[r-1][c-1]
                        
                        
                #분리된 인구에따라 최대최소 차이 갱신
                result = min(max(people_range) - min(people_range), result)

print(result)