[백준 2024/02/20] 17779번 게리맨더링 2

https://www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

 

1. 접근 방법

이 문제는 처음에 5번 구역을 0으로 채운 후, 1, 2, 3, 4번 구역을 나누어서 값을 구하려고 했었다 (5번 구역을 무시하고). 하지만... 그렇지 않을 수 있다는 가능성을 생각하지 못했고 많은 고생을 하였다.

 

하지만, 알고보니 그냥... 직관적으로 나뉜 영역대로 값을 더해주어야 하는 것이었다...ㅜ

우선 4중 for 문으로 x, y, d1, d2의 값을 받아주었다.

for x in range(n):
    for y in range(n):
        for d1 in range(1, n):
            for d2 in range(1, n):

 

따라서, 문제에 나온 대로 5번 선거구 경계선을 그렸다. 이후, 범위를 만족하지 못한다면 continue로 넘어가 주었다.

if x + d1 + d2 >= n or y - d1 < 0 or y + d2 >= n:

 

이후 0으로 값을 채운 n * n 배열을 만들어 주었다. 해당 배열을 population이라고 이름을 붙였다.

각 선거구의 인구수의 합을 저장할 answer이라는 list도 만들었다.

 

이후 문제에 나와 있는대로 선거구의 경계선을 그려주었다.

0으로 값을 채워준 population이라는 2차원 배열에 5의 값을 넣어 경계를 저장해 두었다.

 

다음으로 5번 선거구 내부 채우는 부분이다.

이런식으로 for 문을 돌면서, 5로 값을 저장해 주었다. 이 때, x의 범위는 꼭짓점을 포함하면 안된다. 왜냐하면, 이 for문은 처음 경계를 만났을 때, 채우기 시작하고, 다음 경계를 만났을 때, False로 바꾸어 채우기를 멈추기 때문이다.

하지만, 꼭짓점의 경우 column에 대해서 1개의 값만 가지고 있기 때문에 멈출 수 없기 때문이다.

 

만약 population[r][c] 가 5가 저장되어 있다면, 바로 5번 선거구를 의미하는 answer[4] 에 값을 더해주었다.

그리고 위에 빨간 선으로 그려 놓은 것처럼, 범위에 따라서 각 선거구에 값을 넣어주었다.

 

이후 최소 값을 계속해서 비교해주고 바꾸어 주었다.

answer = float('inf') 를 사용한 것도, infinte 값을 넣어주기 위함이다. 왜냐하면, 최소 값을 찾아야 하기 때문에, 큰 값을 넣어주고 최소 값을 찾아주려 함이다.

 

2. 코드

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

def get_population_diff(x, y, d1, d2):
    global n
    population = [[0] * n for _ in range(n)]
    answer = [0] * 5

    # 5번 선거구 경계선 그리기
    for i in range(d1 + 1):
        population[x + i][y - i] = 5
        population[x + d2 + i][y + d2 - i] = 5
    for i in range(d2 + 1):
        population[x + i][y + i] = 5
        population[x + d1 + i][y - d1 + i] = 5

    # 5번 선거구 내부 채우기
    for i in range(x + 1, x + d1 + d2):
        fill = False
        for j in range(n):
            if population[i][j] == 5:
                fill = not fill
            if fill:
                population[i][j] = 5

    # 각 선거구별 인구수 계산
    for r in range(n):
        for c in range(n):
            if population[r][c] == 5:
                answer[4] += a[r][c]
            elif 0 <= r < x + d1 and 0 <= c <= y:
                answer[0] += a[r][c]
            elif 0 <= r <= x + d2 and y < c < n:
                answer[1] += a[r][c]
            elif x + d1 <= r < n and 0 <= c < y - d1 + d2:
                answer[2] += a[r][c]
            elif x + d2 < r < n and y - d1 + d2 <= c < n:
                answer[3] += a[r][c]

    return max(answer) - min(answer)

answer = float('inf')
for x in range(n):
    for y in range(n):
        for d1 in range(1, n):
            for d2 in range(1, n):
                if x + d1 + d2 >= n or y - d1 < 0 or y + d2 >= n:
                    continue
                answer = min(answer, get_population_diff(x, y, d1, d2))

print(answer)