백준 17779번: 게리맨더링2 (Python)

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

17779번: 게리맨더링 2

접근

따로 특별한 알고리즘은 필요 없는 문제였고, 두가지 코드로 풀 수 있었다.

첫번째 코드는 매우 단순하게 접근하여 풀었고, 코드는 직관적이지만 정답이 구해지는데 시간이 오래걸린다. (x, y, d1, d2)가 될 수 있는 모든 값을 탐색하면서, 각 탐색마다 N * N 모든 위치를 돌면서 matrix[r][c]가 1, 2, 3, 4, 5구역 중 어디에 해당하는지를 구분하여 합산해주었고, 5개 구역의 인구수를 모두 구하고 나면 max값과 min값의 차를 모두 모아 이 중 가장 작은 값을 출력해주었다. 백준 기준 답이 구해지는데 약 2100ms 걸려서 더욱 효율적인 코드를 찾기 위해 추가적인 풀이를 생각하였다.

두번째 코드도 동일하게 가능한 모든 (x, y, d1, d2)를 탐색하지만 5개 구역 인구수를 계산하는 과정을 효율적으로 하기 위해 노력했다. 각각의 요소가 어느 구역에 속해있는지 구분하는 것이 아니라 구역의 경계선을 따라 값을 합산해 주는 방법으로 계산하였고, 추가적으로 (x, y, d1, d2)를 결정할 때도 각 변수들이 서로에게 주는 영향을 고려하여 범위를 제한했다. 결과적으로 280ms 로 첫번째 코드 대비 7배가량 빠르게 정답이 구해지는 것을 확인할 수 있었다.

코드

첫번째 코드

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


def count(x, y, d1, d2):
    # 각 구역의 인구수를 카운트하여 5 구역 간 최대 인구수 차이를 리턴하는 함수
    population = [0] * 5
    for r in range(N):
        for c in range(N):
            if x + y <= r + c <= x + y + 2 * d2 and x - y <= r - c <= x - y + 2 * d1:
                # 5구역에 해당하는 조건
                population[4] += matrix[r][c]
            elif 0 <= r < x + d1 and 0 <= c <= y:
                # 1구역에 해당하는 조건... 이하 생략
                population[0] += matrix[r][c]
            elif 0 <= r <= x + d2 and y < c < N:
                population[1] += matrix[r][c]
            elif x + d1 <= r < N and 0 <= c < y - d1 + d2:
                population[2] += matrix[r][c]
            elif x + d2 < r < N and y - d1 + d2 <= c < N:
                population[3] += matrix[r][c]
    # population 함수의 max 값과 min 값의 차이를 리턴
    return max(population) - min(population)


ans = []
for r in range(0, N - 2):
    for c in range(1, N - 1):
        for d1 in range(1, N - 1):
            for d2 in range(1, N - 1):
                if N <= r + d1 + d2 or c - d1 < 0 or N < c + d2:
                    # 값이 행렬을 벗어나는 경우 생략
                    continue
                ans.append(count(r, c, d1, d2))
print(min(ans))

두번째 코드

N = int(input())
matrix = []
sum_val = 0
for i in range(N):
    tmp = list(map(int, input().split()))
    sum_val += sum(tmp)
    matrix.append(tmp)


def count(x, y, d1, d2, sum_val):
    # 각 구역의 인구수를 카운트하여 5 구역 간 최대 인구수 차이를 리턴하는 함수
    population = [0] * 5
    # r, lc, rc : r 행에서 5구역을 구분하는 가장 왼쪽값 lc 와 가장 오른쪽 값 rc
    r, lc, rc = 0, y, y + 1
    while r < N:
        if r < x:
            # 5구역에 도달하기 전 r 행에서 1구역과 2구역에 해당하는 인구수 계산
            population[0] += sum(matrix[r][: (y + 1)])
            population[1] += sum(matrix[r][(y + 1) :])
        elif x + d1 + d2 < r:
            # 5구역을 지나친 후 r 행에서 3구역과 4구역에 해당하는 인구수 계산
            population[2] += sum(matrix[r][: (y + d2 - d1)])
            population[3] += sum(matrix[r][(y + d2 - d1) :])
        else:
            # 5구역이 존재하는 r 행에서
            # lc 는 x + d1 행 전까지 1구역, 이후에는 3구역
            if r < x + d1:
                population[0] += sum(matrix[r][:lc])
                lc -= 1
            else:
                population[2] += sum(matrix[r][:lc])
                lc += 1
            # rc 는 x + d2 행까지 2구역, 이후에는 4구역
            if r < x + d2:
                population[1] += sum(matrix[r][rc:])
                rc += 1
            elif r == x + d2:
                population[1] += sum(matrix[r][rc:])
                rc -= 1
            else:
                population[3] += sum(matrix[r][rc:])
                rc -= 1
        r += 1
    #전체 인구에서 1,2,3,4 구역 합을 빼주어 5구역 인구수를 계산
    population[4] = sum_val - sum(population[:4])
    return max(population) - min(population)


ans = []
for d2 in range(1, N - 2):
    for d1 in range(1, N - d2):
        for c in range(d1, N - d2):
            for r in range(0, N - d1 - d2):
                ans.append(count(r, c, d1, d2, sum_val))
print(min(ans))

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!