[SWEA 완전탐색] 파리퇴치(4중 포문 이용!)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq

SW Expert Academy

 

N과 M, 그리고 N*N 안을 채우는 값들이 제시되고,

N*N 판 위에서 M*M 모양 안에 들어오는 판 요소들의 합 중에서 최댓값을 구하는 문제이다.

 

처음에는 아래와 같이 코드를 3중 포문으로 작성하였다.

T = int(input())
for t in range(1, T+1):
    n,m = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    max, temp = 0, 0
    for cnt in range(n-m+1): # 0 1 2
        for f in range(cnt,cnt+m): # 0 1 2
            for s in range(cnt,cnt+m): # 0 1 2
                temp += arr[f][s]
            
        if max < temp:
            max = temp
        temp = 0
    print(f'#{t} {max}')

예시 출력값으로 나온

#1 49
#2 159

는 정답 처리되어서 제출해봐도 계속 오답을 뱉어내었다.

 

예제 출력과 같아 보이는 코드는 '맞았다는 착각'때문에 오히려 문제 해결 코드를 완성하는데 어려움을 겪게되는 것 같다.

결국 그리드를 하나씩 그려가면서 위의 코드가 왜 오답인지 파악했는데

하나의 기준으로만 가로, 세로를 이동시키다 보니 오로지 대각선 방향으로만 탐색하고 있었다.

가령 6x6 그리드에서 2x2 크기 대각선으로만 이동하는 경향성으로 인하여 오른쪽 상단이나 왼쪽 하단과 같이 대각선에서 벗어난 부분을 전혀 탐색하지 않게 된다.

결국 예제 출력 답이 맞았던 이유는 대각선 안의 M*M에서 최댓값이 있었기 때문이었다.

 

따라서 아래와 같이 코드를 변경하고 pass를 볼 수 있었다.

하나의 기준이 아닌 start_row, start_col 이라는 2개의 기준치를 두고 이동함으로써 행쪽으로도 열쪽으로도 이동하는 모든 M*M 케이스를 탐색할 수 있는 것이다.

T = int(input())
for t in range(1, T + 1):
    n, m = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    max_sum = 0

    for start_row in range(n - m + 1):# 0 1 2
        for start_col in range(n - m + 1): # 0 1 2
            temp = 0
            for row in range(start_row, start_row + m): # 0 1 2
                for col in range(start_col, start_col + m): # 0 1 2
                    temp += arr[row][col]
            
            if temp > max_sum:
                max_sum = temp

    print(f'#{t} {max_sum}')