[백준 17779] 게리맨더링 2

문제 보기

이 문제는 브루트 포스 문제이다.

모든 경우의 수를 따져서 문제에 조건에 해당하는 최적의 결과를 찾아야 하는 게 목적이다.

모든 경우의 수를 따질 대상은 기준점이 되는 (x, y)와 d1, d2이다. (81~84번째 줄)

그리고 각 경우가 유효한 경우인지는 다음과 같이 문제에 명시되어 있으므로 이를 적용해서 필터링한다. (85번째 줄)

문제에 명시된 선거구를 나누는 방법

 

맨 처음 문제를 풀 때 다음과 같은 로직으로 문제를 해결하려고 했다.

1. 5번 선거구의 경계를 구한다.
2. 5번 선거구에 포함된 인구를 구한다.
3. 1, 2, 3, 4번 선거구에 포함된 인구를 구한다.
4. 인구가 가장 많은 선거구와 가장 적은 선거구의 차이가 최소가 되는 경우를 찾는다.

그런데 2번 과정에서 5번 선거구에 포함된 인구를 구할 방법이 떠오르지 않았다.

문제를 계속해서 고민하던 도중 다음과 같은 생각이 떠올랐다.

문제에 1번~4번 선거구에 해당하는 조건이 명시되어 있으니, 차라리 1번~4번 선거구의 인구를 먼저 구하고, 전체 인구에서 각 선거구의 인구를 빼면 5번 선거구의 인구를 구할 수 있겠다!

 

문제를 푼 로직은 다음과 같다.

1. 새로운 2차원 배열(temp_board)에 5번 선거구의 경계를 구하고, 이를 표시한다. (13~29번째 줄)
2. 1번에서 표시해놓은 5번 선거구의 경계를 사용하여 1번~4번 선거구에 포함된 인구를 구한다. 그리고 각 선거구의 인원을 구할 때, 최대 선거구 인원과 최소 선거구 인원을 갱신한다. (31~69번째 줄)
3. 전체 인구에서 1번~4번 선거구의 인원을 빼서 5번 선거구의 인원을 구한다. 그리고 최대 선거구 인원과 최소 선거구 인원을 갱신한다. (71~74번째 줄)
4. 최대 선거구 인원과 최소 선거구 인원의 차를 구한다. (76번째 줄)
5. 모든 경우의 수에 대해서 1번~4번 과정을 반복하여 최대 선거구 인원과 최소 선거구 인원의 차가 최소가 되는 정답을 찾는다. (81~86번째 줄)

 

2번에서 말한 5번 선거구의 경계를 사용했다는 말은 다음과 같다.

각 선거구를 탐색하는 순서는 원 안에 표시된 순서와 같다.

5번 선거구의 경계를 만나면 바로 다음 행의 탐색으로 넘어간다. (지금 생각해보니 2번, 4번 선거구의 행을 순회할 때 굳이 밑에서부터 올라갈 필요가 없다... 위에서 아래로 탐색하는 게 더 이해하기 편할 것 같다.)

위와 같이 1번~4번 선거구의 인구를 먼저 구하면 복잡하게 5번 선거구의 인구를 고려할 필요가 없어지게 된다.

 

import sys
 
n = int(sys.stdin.readline())
A = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for r in range(1, n + 1, 1):
    line = list(map(int, sys.stdin.readline().split()))
    for c in range(1, n + 1, 1):
        A[r][c] = line[c - 1]
 
 
def solution(x, y, d1, d2):
    max_sum, min_sum = 0, sys.maxsize
    temp_board = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    
    # border 1
    for d in range(0, d1 + 1, 1):
        temp_board[x + d][y - d] = 5
    
    # border 2
    for d in range(0, d2 + 1, 1):
        temp_board[x + d][y + d] = 5
    
    # border 3
    for d in range(0, d2 + 1, 1):
        temp_board[x + d1 + d][y - d1 + d] = 5
    
    # border 4
    for d in range(0, d1 + 1, 1):
        temp_board[x + d2 + d][y + d2 - d] = 5
    
    # sum of sector 1
    sum1 = 0
    for i in range(1, x + d1):
        for j in range(1, y + 1, 1):
            if temp_board[i][j] == 5:
                break
            sum1 += A[i][j]
    max_sum = max(max_sum, sum1)
    min_sum = min(min_sum, sum1)
        
    # sum of sector 2
    sum2 = 0
    for i in range(x + d2, 0, -1):
        for j in range(n, y, -1):
            if temp_board[i][j] == 5:
                break
            sum2 += A[i][j]
    max_sum = max(max_sum, sum2)
    min_sum = min(min_sum, sum2)
        
    # sum of sector 3
    sum3 = 0
    for i in range(x + d1, n + 1, 1):
        for j in range(1, y - d1 + d2, 1):
            if temp_board[i][j] == 5:
                break
            sum3 += A[i][j]
    max_sum = max(max_sum, sum3)
    min_sum = min(min_sum, sum3)
        
    # sum of sector 4
    sum4 = 0
    for i in range(n, x + d2, -1):
        for j in range(n, y - d1 + d2 - 1, -1):
            if temp_board[i][j] == 5:
                break
            sum4 += A[i][j]
    max_sum = max(max_sum, sum4)
    min_sum = min(min_sum, sum4)
    
    # sum of sector 5
    sum5 = total - (sum1 + sum2 + sum3 + sum4)
    max_sum = max(max_sum, sum5)
    min_sum = min(min_sum, sum5)
    
    return max_sum - min_sum
 
 
total = sum(map(sum, A))
answer = total
for r in range(1, n + 1, 1):
    for c in range(1, n + 1, 1):
        for d1 in range(1, n + 1, 1):
            for d2 in range(1, n + 1, 1):
                if 1 < r + d1 + d2 <= n and 1 <= c - d1 < c + d2 <= n:
                    answer = min(answer, solution(r, c, d1, d2))
print(answer)