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

문제 보기

브루트포스, 구현, 시뮬레이션 문제이다.

선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구하면 된다.

 

브루트포스를 구현하기 위해서는 1번 조건에 맞는 x, y, d1, d2 값이 필요하다.

1번 조건: d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N

x, y, d1, d2는 1 이상 n이하이기 때문에 밑줄 친 부분의 조건만 추가하면 1번 조건을 만족한다.

 

추가적으로 2번 경계선 조건에 해당하는 위치에 5를 대입하고, 선거구를 구별하면 된다.

경계선 조건과 선거구 구별 또한 문제에서 주어진 조건을 그대로 코드로 작성하면 된다.

 

코드

import copy

INF = 1e9


def solve(x, y, d1, d2):
    temp = [[0] * (n + 1) for _ in range(n + 1)]
    # 2번 조건
    temp[x][y] = 5
    for i in range(1, d1 + 1):
        temp[x + i][y - i] = 5
    for i in range(1, d2 + 1):
        temp[x + i][y + i] = 5
    for i in range(1, d2 + 1):
        temp[x + d1 + i][y - d1 + i] = 5
    for i in range(1, d1 + 1):
        temp[x + d2 + i][y + d2 - i] = 5

    people = [0] * 5
    # 1번 선거구
    for r in range(1, x + d1):
        for c in range(1, y + 1):
            if temp[r][c] == 5:
                break
            else:
                people[0] += maps[r][c]

    # 2번 선거구
    for r in range(1, x + d2 + 1):
        for c in range(n, y, -1):
            if temp[r][c] == 5:
                break
            else:
                people[1] += maps[r][c]

    # 3번 선거구
    for r in range(x + d1, n + 1):
        for c in range(1, y - d1 + d2):
            if temp[r][c] == 5:
                break
            else:
                people[2] += maps[r][c]

    # 4번 선거구
    for r in range(x + d2 + 1, n + 1):
        for c in range(n, y - d1 + d2 - 1, -1):
            if temp[r][c] == 5:
                break
            else:
                people[3] += maps[r][c]

    # 5번 선거구
    people[4] = total - sum(people)
    return max(people) - min(people)


if __name__ == "__main__":
    n = int(input())
    maps = [[0] * (n + 1)] + [[0] + list(map(int, input().split())) for _ in range(n)]

    total = 0
    for i in range(1, n + 1):
        total += sum(maps[i])

    answer = INF
    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):
                    # 1번 조건
                    if x + d1 + d2 > n:
                        continue
                    if y - d1 < 1:
                        continue
                    if y + d2 > n:
                        continue

                    answer = min(answer, solve(x, y, d1, d2))

    print(answer)