1. 문제 소개

840. Magic Squares In Grid

2. 나의 풀이

어려운 문제라기보다는 엣지 케이스를 잘 고려해야하는 문제였다.
시간복잡도는 $O(n\times m)$이다.

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])                    # n: 행 개수, m: 열 개수
        ans = 0                                           # 마방진 개수 누적

        if n < 3 or m < 3:                                # 3x3을 만들 수 없으면
            return 0                                      # 결과는 0

        for r in range(n-2):                              # 3x3의 좌상단 행 인덱스 r
            for c in range(m-2):                          # 3x3의 좌상단 열 인덱스 c
                nums = [False] * 10                       # 1~9 사용 여부 체크(인덱스 0은 사용 안 함)
                stop = False                               # 현재 3x3이 조건 위반인지 표시

                # 1) 3x3 내 모든 값이 1~9 범위이고 중복이 없는지 검사
                for x in range(3):                        # 3x3 내부 행 오프셋
                    for y in range(3):                    # 3x3 내부 열 오프셋
                        v = grid[r+x][c+y]                # 현재 값
                        if v < 1 or v > 9 or nums[v]:     # 범위 밖이거나 이미 등장한 값이면
                            stop = True                   # 실패 처리
                            break                         # 내부 루프 탈출
                        nums[v] = True                    # 값 v 사용 표시
                    if stop:                               # 중간에 실패하면
                        break                              # 바깥 루프도 탈출
                if stop:                                   # 값/중복 검사에서 실패면
                    continue                               # 다음 3x3로 넘어감

                # 2) 3x3 마방진(1~9)에서 중앙값은 반드시 5라는 성질로 빠른 가지치기
                if grid[r+1][c+1] != 5:
                    continue

                # 3) 행 합 검사(각 행의 합이 15인지)
                for x in range(3):
                    if grid[r+x][c] + grid[r+x][c+1] + grid[r+x][c+2] != 15:
                        stop = True                         # 조건 위반 표시(즉시 break는 하지 않음)

                # 4) 열 합 검사(각 열의 합이 15인지)
                for y in range(3):
                    if grid[r][c+y] + grid[r+1][c+y] + grid[r+2][c+y] != 15:
                        stop = True                        # 조건 위반 표시

                # 5) 주대각선 합 검사
                if grid[r][c] + grid[r+1][c+1] + grid[r+2][c+2] != 15:
                    stop = True

                # 6) 부대각선 합 검사
                if grid[r][c+2] + grid[r+1][c+1] + grid[r+2][c] != 15:
                    stop = True

                if not stop:                               # 모든 조건을 만족하면
                    ans += 1                               # 마방진 개수 증가

        return ans                                         # 최종 개수 반환

3. 다른 풀이

다른 풀이는 찾아보지 않았다.

4. 마무리

엣지 케이스를 잘 고려하자.