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

17779번: 게리맨더링 2

완전탐색과 구현 문제입니다. 가능한 모든 경계선 d1, d2의 경우의 수를 구한뒤 그 경우의 수에대하여 경계선을 만들고, 그 경계선으로부터의 지역들을 분리시키고, 분리된 지역으로부터 인구수를 구한뒤 가장많은 인구수와 가장적은 인구수의 차이의 최소값을 구하면 됩니다.

1. 모든 경우의수 탐색
   1. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N) 에 맞는 d1, d2를 구한다.
2. 해당 탐색 구역에서의 경계선 만들기
   1. 경계선을 만드는 조건으로 경계선을 만든다.
   2. 경계선을 기준으로 1구역과 2구역 3구역 4구역의 그래프를 채운다.
   3. 각각의 열과 행에대하여 경계선의 조건에따라서 그래프를 순회하며 채운다.
   4. 1구역 2구역 3구역 4구역으로 나누면서 각각의 구역에 대하여 인구수 누적값을 구한다.
   5. 5구역은 전체인구수 - (1, 2, 3, 4) 구역 이다.
3. 가장많은 선거구와 가장 적은 선거구의 차이값을 계산한뒤 구하고자하는 최소값의 가중치에 반영한다.

import sys
input = sys.stdin.readline

N = int(input())
total = 0
table = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1, N+1):
    temp = list(map(int, input().split()))
    for j in range(1, N+1):
        table[i][j] = temp[j-1]
def solve(x, y, d1, d2):
    city = [[0 for _ in range(N+1)] for _ in range(N+1)]
    # 경계선을 만든다.
    # 1번 경계선
    people = [0 for _ in range(5)]
    for t in range(d1+1):
        city[x+t][y-t] = 5

    # 2번 경계선
    for t in range(d2+1):
        city[x+t][y+t] = 5

    # 3번 경계선
    for t in range(d2+1):
        city[x+d1+t][y-d1+t] = 5

    # 4번 경계선
    for t in range(d1+1):
        city[x+d2+t][y+d2-t] = 5

    # 1번 도시
    for i in range(1, x+d1+1):
        for j in range(1, y+1):
            if city[i][j] == 5:
                break
            city[i][j] = 1

    # 2번 도시
    for i in range(1, x+d2+1):
        for j in range(N, y, -1):
            if city[i][j] == 5:
                break
            city[i][j] = 2

    # 3번 도시
    for i in range(x+d1, N+1):
        for j in range(1, y-d1+d2):
            if city[i][j] == 5:
                break
            city[i][j] = 3

    # 4번 도시
    for i in range(x+d2+1, N+1):
        for j in range(N, y+d2-d1-1, -1):
            if city[i][j] == 5:
                break
            city[i][j] = 4

    for i in range(1, N+1):
        for j in range(1, N+1):
            if city[i][j] == 0 or city[i][j] == 5:
                people[4] += table[i][j]
            elif city[i][j] == 1:
                people[0] += table[i][j]
            elif city[i][j] == 2:
                people[1] += table[i][j]
            elif city[i][j] == 3:
                people[2] += table[i][j]
            elif city[i][j] == 4:
                people[3] += table[i][j]

    result = abs(max(people) - min(people))
    return result

ans = 100 * 21 * 21
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):
                if N >= x + d1 + d2 and y-d1 >= 1 and N >= y+d2:
                    ans = min(solve(x ,y, d1, d2), ans)

print(ans)

<aside> 💡 경계선을 나누고 구역을 분리하는데에 있어서 굉장히 머리가 아팠던 문제 였습니다. 아이디어가 떠오르지 않아 인터넷에 아이디어를 찾아보니, 경계선을 만들고 테이블을 순회하면서 경계선을 기준으로 구역을 나누었습니다.

</aside>