🐹 게리맨더링2

1. 문제 링크

17779번: 사다리 타기

2. 코드

Python3 34260KB 3588ms

N = int(input())
city = []
for _ in range(N):
    city.append(list(map(int, input().split())))
INF = int(1e9)

from itertools import product
from collections import deque

numbers = [i for i in range(N+1)]
result = INF
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def check_boundary(x, y, d1, d2):
    boundary1 = [(x + i, y - i) for i in range(d1+1)]
    boundary2 = [(x + i, y + i) for i in range(d2+1)]
    boundary3 = [(x + d1 + i, y - d1 + i) for i in range(d2+1)]
    boundary4 = [(x + d2 + i, y + d2 - i) for i in range(d1+1)]
    all_boundary = list(set(boundary1 + boundary2 + boundary3 + boundary4))
    for boundary in all_boundary:
        r, c = boundary
        area_info[r][c] = 5
    
    return all_boundary

def check_area5(boundary):
    boundary_dict = {}
    for b in boundary:
        x, y = b
        if x in boundary_dict:
            boundary_dict[x].append(y)
        else:
            boundary_dict[x] = [y]
    
    # 경계선 안을 5로 채우기
    for k in boundary_dict.keys():
        if len(boundary_dict[k]) == 1:
            continue
        start, end = min(boundary_dict[k]), max(boundary_dict[k])
        for i in range(start + 1, end):
            area_info[k][i] = 5

def check_other_area(sx, sy, ex, ey, area_num):
    q = deque([])
    # 4일때만 끝지점에서 탐색
    if area_num == 4:
        q.append((ex, ey))
        area_info[ex][ey] = area_num
    else:
        q.append((sx, sy))
        area_info[sx][sy] = area_num
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if sx <= nx <= ex and sy <= ny <= ey and area_info[nx][ny] == 0:
                area_info[nx][ny] = area_num
                q.append((nx, ny))

def check_area_people():
    for i in range(N):
        for j in range(N):
            area_people[area_info[i][j]-1] += city[i][j]

for p in product(numbers, repeat=4):
    x, y, d1, d2 = p
    # 기준점이 재현시 밖이거나 이동 거리가 0일 때 
    if x == N or y == N or d1 == 0 or d2 == 0:
        continue
    # 경계 중 한 값이라도 재현시 밖일 때
    if x + d1 >= N or y - d1 < 0 or x + d2 >= N or y + d2 >= N or x + d2 + d1 >= N or y + d2 - d1 < 0 or y + d2 - d1 >= N:
        continue
    area_info = [[0] * N for _ in range(N)]
    area_people = [0] * 5
    boundary = check_boundary(x, y, d1, d2)
    check_area5(boundary)   # 5구역 체크
    check_other_area(0, 0, x + d1 - 1, y, 1)       # 1구역 체크
    check_other_area(0, y + 1, x + d2, N-1, 2)      # 2구역 체크
    check_other_area(x + d1, 0, N-1, y - d1 + d2 - 1, 3)   # 3구역 체크
    check_other_area(x + d2 + 1, y - d1 + d2, N-1, N-1, 4) # 4구역 체크
    check_area_people() # 구역별 사람수 확인
    area_people.sort()
    diff = area_people[4] - area_people[0]  # 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이
    result = min(result, diff)

print(result)

3. 해설

area_info는 각 구역 번호를 저장한다.

주어진 경계선 위치의 값을 5로 저장하고, 경계선 안의 값도 5로 초기화한다. 이때 다른 구역과는 다르게 bfs를 사용해서 값을 채우면 5로 둘러싸인 공간에는 값을 넣을 수 없으므로 경계선마다 x값에 해당하는 y구역 내의 위치를 모두 5로 초기화한다.

나머지 1,2,3,4 구역은 bfs를 사용하여 구역 번호를 저장한다. 이때 1,2,3 구역은 각 시작 부분부터 탐색하지만 4구역의 시작부분은 5구역과 겹치게 되므로 마지막 부분(N-1, N-1)부터 탐색한다.

각 구역번호를 저장했으면 구역번호별로 인원수를 area_people에 저장한다.

area_people을 정렬한 후 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이 즉, 리스트의 마지막 값과 첫 번째 값의 차를 구한 후 결과값과 비교하여 최솟값을 저장한다.