[LeetCode] 54. Spiral Matrix - Python

https://leetcode.com/problems/spiral-matrix/description/?envType=study-plan-v2&envId=top-interview-150

Spiral Matrix - LeetCode

다양한 풀이가 있을 것 같은 구현문제였다. (삼성 기출에서도 나올법하다고 생각됨.)

해당 미로를 BFS 탐색하듯이 생각하면 구현하기 편한 방법으로 풀 수 있다. 

회전을 해야할 지점을 잡는 것이 이 문제의 핵심인데, 이를 간단히 체크하기 위해서 배열이 범위를 초과하거나 이미 방문처리되었거나 하면 방향을 전환시켜주도록 분기처리했다. 

 

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        answer = []
        N = len(matrix)
        M = len(matrix[0])

        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        i, j = 0, 0
        visited = [[False] * M for _ in range(N)]
        k = 0 # direction
        
        for _ in range(N*M):
            answer.append(matrix[i][j])
            visited[i][j] = True 
            
            i, j = i + dx[k], j + dy[k]
            if not (0 <= i < N and 0 <= j < M) or visited[i][j]:
                i, j = i - dx[k], j - dy[k]
                k = (k+1) % 4
                i, j = i + dx[k], j + dy[k]



        return answer