[구름] 놀이공원 - 파이썬

문제

🔗 : https://level.goorm.io/exam/88520/놀이공원/quiz/1

어느 한 도시에서는 공장 부지가 부도가 나게 되어 넓은 공터가 경매에 올라오게 되었다.

이 공터는 가로와 세로 길이가 각각 N인 정사각형 모양이며, 가로와 세로 길이가 1인 정사각형 격자 모양으로 영역을 나누어 개별적으로 판매하고 있다.

 

그 도시에 살고있던 한 부자 경영인은 평소 자신이 기획해오던 놀이공원 건설 프로젝트를 몰래몰래 진행하기로 결정하였다. 때마침 경매에 올라온 이 공터에 관심을 가지게 된 경영인은 판매 중인 땅들 중 일부에 기존의 공장에서 배출된 폐기물들이 방치되어 있다는 사실을 알게 되었다. 놀이공원 건설을 위해서는 가로와 세로 길이가 K인 정사각형 모양의 영역이 필요한데, 당연히 놀이공원 건설을 위해서는 해당 영역의 폐기물들을 모두 처리해야만 한다.

 

NxN 격자 모양의 공터에서 KxK 크기의 땅을 구매하려고 할 때, 구매할 땅에 포함된 폐기물의 수를 최소화하는 영역을 찾는 프로그램을 작성하라.

 

예제 설명

첫 번째 예제에서 공원의 정보는 아래 그림과 같고, 3x3 크기의 영역을 선택해야 한다.

가운데 그림과 같이 파란색 영역을 선택하면 세 개의 폐기물을 처리해야 하지만,

오른쪽 그림과 같이 주황색 영역을 선택하면 한 개의 폐기물만 처리하면 된다.

다른 어떤 영역을 골라도 최소 한 개 이상의 폐기물을 처리해야 하므로, 답으로는 1을 출력해야 한다.

 

입력

첫째 줄에는 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스의 입력은 아래와 같은 형식을 따른다.

 

첫째 줄에는 공터의 크기를 나타내는 N과 구매할 땅의 크기를 나타내는 K가 공백을 두고 주어진다.

다음 N개의 줄에는 공터의 정보를 나타내는 정수가 한 줄에 N개씩 공백을 두고 주어진다. 주어지는 정수는 0 또는 1이며, 0은 해당 칸이 비어있음을, 1은 해당 칸에 폐기물이 있음을 의미한다.

 

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 100
• 1 ≤ K ≤ M
• 입력에서 주어지는 수는 모두 정수이다.

 

출력

각 테스트 케이스에 대해, KxK 모양의 땅을 구매했을 때 처리해야 하는 최소 폐기물의 수를 한 줄에 하나씩 출력한다.

 

예시 1

입력

1
5 3
1 0 0 1 0
0 1 0 0 1
0 0 0 1 0
0 0 0 0 0
0 0 1 0 0

출력

1

 

---

C++로는 단순히 NxN의 배열 내에서 KxK 만큼 윈도우 슬라이딩 해가며 최솟값을 찾아도 시간초과가 안걸리지만,

파이썬으로는 그렇게 풀었다가는 테스트케이스의 반도 못맞춘다.

 

누적합을 이용해서 풀어야 하는 문제.

누적합 알고리즘 설명: https://miiinnn23.tistory.com/106

[알고리즘] 누적 합(prefix sum)

 

단순히 공원에 있는 폐기물의 수의 누적합을 배열에 저장하고,

처음부터 끝까지 돌아주면서 KxK 구역 내 최소 합을 찾으면 된다.

 

C++로도 누적합 써서 다시 풀어봤는데, CPU 계산 시간이나 실행시간을 확인해보면 확연하게 시간차이가 발생한다.

코드 수정 전 -> 코드 수정 후

 

코드

# using prefix sum
T = int(input())

for _ in range(T):
    N, K = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]

    prefix_sum = [[0] * (N + 1) for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, N + 1):
            prefix_sum[i][j] = (board[i - 1][j - 1]
                                + prefix_sum[i - 1][j]
                                + prefix_sum[i][j - 1]
                                - prefix_sum[i - 1][j - 1]) # 겹치는 부분 제외
    
    answer = N * N
    for y in range(N - K + 1):
        for x in range(N - K + 1):
            total = (prefix_sum[y + K][x + K]
                     - prefix_sum[y][x + K]
                     - prefix_sum[y + K][x]
                     + prefix_sum[y][x])
            
            answer = min(answer, total)
    
    print(answer)