17779: 게리맨더링 2

풀이 시간

• 2h 20m
• list 인덱싱 때문에 대가리 깨질뻔..

구현 방법

• N이 작기 때문에 brute force로 모든 경우의 x, y, d1, d2를 찾고, 인구수 차이의 최솟값을 구해야함
• • 4중 for문을 돌며 문제의 조건에 맞는 x, y, d1, d2를 찾음
• • 그 후 해당 x, y, d1, d2에 맞는 경계선을 그리고 solution()을 호출
• solution()
• • 1번 선거구, 2번 선거구, 3번 선거구, 4번 선거구 각각의 인구수를 구함 (5번 선거구는 total_population에서 1, 2, 3, 4번 선거구의 인구수를 뺌)
• • 각 선거구마다 문제의 조건에 맞게 2중 for문을 돌며, 경계선을 만나기 전까지 인구수를 더해줌
    -> 경계선을 만난 경우 break하고 다음 row 탐색

• 이 문제에선 조건에 맞지 않는 x, y, d1, d2를 거르는 과정과 각 구역을 인덱싱해주는 부분이 어려웠다

코드

import sys


def solution(x, y, d1, d2):
    global total_poplutaion
    population = [0, 0, 0, 0, 0]

    #1번 선거구
    for r in range(0, x+d1):
        for c in range(0, y+1):
            if area[r][c] == 5:
                break 
            population[0] += board[r][c]

    #2번 선거구
    for r in range(0, x+d2+1):
        for c in range(N-1, y, -1):
            if area[r][c] == 5:
                break
            population[1] += board[r][c]

    #3번 선거구
    for r in range(x+d1, N):
        for c in range(0, y-d1+d2):
            if area[r][c] == 5:
                break
            population[2] += board[r][c]

    #4번 선거구
    for r in range(x+d2+1, N):
        for c in range(N-1, y-d1+d2-1, -1):
            if area[r][c] == 5:
                break
            population[3] += board[r][c]

    #5번 선거구
    population[4] = total_poplutaion - sum(population)

    return abs(max(population) - min(population))


N = int(sys.stdin.readline()[:-1])
board = []; total_poplutaion = 0
for n in range(N):
    tmp = list(map(int, sys.stdin.readline()[:-1].split()))
    total_poplutaion += sum(tmp)
    board.append(tmp)

result = 10e9
for x in range(N):
    for y in range(N):
        for d1 in range(1, N+1):
            for d2 in range(1, N+1):
                if x+d1+d2 > N-1 or y-d1 <0 or y+d2 > N-1:
                    continue
                # 경계선 그리기
                area = [[0] * N for _ in range(N)]
                area[x][y] = 5
                for i in range(1, d1+1):
                    area[x+i][y-i] = 5
                for i in range(1, d2+1):
                    area[x+i][y+i] = 5
                for i in range(1, d2+1):
                    area[x+d1+i][y-d1+i] = 5
                for i in range(1, d1+1):
                    area[x+d2+i][y+d2-i] = 5

                result = min(result, solution(x, y, d1, d2))
                    
print(result)

결과