[코드트리] 최고의 33위치 / 완전탐색

 

https://www.codetree.ai/missions/2/problems/best-place-of-33?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

최고의 33위치

---

N * N 크기의 격자 정보가 주어집니다. 이때 해당 위치에 동전이 있다면 1, 없다면 0이 주어집니다. N * N 격자를 벗어나지 않도록 3 * 3 크기의 격자를 적절하게 잘 잡아서 해당 범위 안에 들어있는 동전의 개수를 최대로 하는 프로그램을 작성해보세요

 

입력 형식

첫 번째 줄에는 격자의 크기를 나타내는 N이 주어집니다.

두 번째 줄부터는 N개의 줄에 걸쳐 격자에 대한 정보가 주어집니다. 각 줄에는 각각의 행에 대한 정보가 주어지며, 이 정보는 0또는 1로 이루어진 N개의 숫자로 나타내어지며 공백을 사이에 두고 주어집니다.

• 3 ≤ N ≤ 20

출력 형식

N * N 격자를 벗어나지 않으면서, 3 * 3 크기 격자 내에 들어올 수 있는 최대 동전의 수를 출력해주세요.

 

입출력 예제

예제1

입력:

3
1 0 1
0 1 0
0 1 0

 

출력:

4

 

 

내가 짠 코드

---

import sys
n = int(input())

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

ans = -sys.maxsize
sum = 0

#시작점구하기
for i in range(n-2):
    for j in range(n-2):
        sum = 0
        #3*3 의 1의 개수 구하기
        for k in range(i, i+3):
            for m in range(j,j+3):
                sum += arr[k][m]
        ans = max(sum,ans)

print(ans)

배열을 순회하는 완전 탐색문제이다. 3x3 행렬에 가장 많이 1이 들어갈 때 그 갯수를 구해야한다.

완전 탐색 시에는 기준을 정하는 것이 중요하다. 

 

이 문제에서는 3x3 행렬로 nxn 행렬을 순회하기 위해 3x3 행렬의 시작점을 돌아가면서 고정 시켜두고, 합을 구하였다. 

이때, 범위 설정이 중요한데 시작점은 (0,0) 에서 시작하고, 마지막 점은 n-3, n-3 번째 여야 인덱스에 넘어가지 않을 것이다.

(시작점이 (n-3, n-3) 일때 시작점으로 부터 n-3, n-2, n-1 행까지와 n-3, n-2, n-1 열까지의 3x3 행렬을 탐색하므로)

이때 range() 함수에서 끝점은 미포함이므로 n-2 로 설정해야한다.