[LeetCode] 54. Spiral Matrix (medium, python)

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

Spiral Matrix - LeetCode

아이디어

방향 벡터(dv)를 사용해서 풀었다.

시작점(0,0)에서 우측 방향으로 이동하다가 범위를 벗어나거나 이미 방문한 곳(visited[nx][ny] == 1)이면 방향을 시계방향으로 90도 돌려준 뒤(d = (d+1)%4) 해당 방향으로 이동하도록 했다. 

 

전체 코드

# 12:11 ~ 12:24(13")

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        dv = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        N, M = len(matrix), len(matrix[0])
        visited = [[0 for _ in range(M)] for y in range(N)]

        x, y, d = 0, 0, 1
        visited[0][0] = 1
        answer = [matrix[0][0], ]

        while True:
            if len(answer) == N*M:
                break
            
            nx = x + dv[d][0]
            ny = y + dv[d][1]

            if nx < 0 or nx >= N or ny < 0 or ny >= M or visited[nx][ny] == 1:
                d = (d+1) % 4
                continue
            
            answer.append(matrix[nx][ny])
            visited[nx][ny] = 1
            x, y = nx, ny
            
        return answer