LeetCode 54 - Spiral Matrix

행렬의 원소를 바깥쪽부터 시계 방향 나선 순서로 반환하는 Medium 문제다. 위·오른쪽·아래·왼쪽 경계를 줄여가는 방법도 있지만, 이번에는 현재 위치와 방향을 상태로 두고 다음 칸에 갈 수 없을 때 오른쪽으로 회전하는 simulation 방식으로 풀었다.

---

문제 링크 & 설명

• 문제 링크: 54. Spiral Matrix
• 요약: m × n 행렬의 모든 원소를 오른쪽, 아래, 왼쪽, 위 순서로 방향을 바꿔가며 나선형으로 방문한 결과를 반환한다.

행렬의 모든 칸을 정확히 한 번 방문해야 한다. 다음 좌표가 범위를 벗어나거나 이미 방문한 칸이면 방향을 바꾸고, 결과 배열의 길이가 전체 칸 수에 도달할 때까지 반복한다.

---

접근 방법

방향 인덱스 0, 1, 2, 3을 오른쪽, 아래, 왼쪽, 위에 대응시켰다. 현재 방향의 다음 좌표를 계산한 뒤 이동할 수 없다면 (dir + 1) % 4로 시계 방향 회전을 처리한다.

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

next_row = row + dr[dir]
next_col = col + dc[dir]

별도 visited 배열을 만들지 않고 방문한 칸의 값을 -200으로 바꿨다. 문제에서 주어지는 원소 범위 밖의 값을 표시값으로 사용했기 때문에, 실제 입력값과 충돌하지 않는다.

if (
    next_row < 0
    or next_row >= n
    or next_col < 0
    or next_col >= m
    or matrix[next_row][next_col] == VISIT
):
    dir = (dir + 1) % 4

matrix[row][col] = VISIT

이 방식은 입력 행렬을 변경한다. 원본을 보존해야 하는 조건이라면 visited 배열을 따로 두거나, top·bottom·left·right 경계를 줄이는 방식이 더 적합하다.

---

복잡도 분석

• 시간 복잡도: O(m × n)
  • 모든 셀을 정확히 한 번 결과에 추가한다.
• 공간 복잡도: O(1)
  • 반환할 결과 배열을 제외하면 방향 배열과 위치 변수만 사용한다. 방문 상태는 입력 행렬에 직접 기록한다.

---

구현 코드

from typing import List

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

        dir = 0
        row = 0
        col = 0

        n = len(matrix)
        m = len(matrix[0])
        size = n * m

        VISIT = -200
        dr = [0, 1, 0, -1]
        dc = [1, 0, -1, 0]

        while len(answer) < size:
            item = matrix[row][col]
            answer.append(item)

            next_row = row + dr[dir]
            next_col = col + dc[dir]

            if (
                next_row < 0
                or next_row >= n
                or next_col < 0
                or next_col >= m
                or matrix[next_row][next_col] == VISIT
            ):
                dir = (dir + 1) % 4

            matrix[row][col] = VISIT

            row += dr[dir]
            col += dc[dir]

        return answer

---

요약 및 회고

나선형 순회를 여러 개의 반복문으로 나누지 않고, 이동할 수 없을 때 방향을 바꾸는 하나의 규칙으로 표현했다. 덕분에 직사각형 행렬에서도 같은 흐름을 유지할 수 있었다. 입력을 방문 배열처럼 활용해 추가 공간을 줄였지만 원본이 바뀐다는 비용도 있으므로, 실제 상황에서는 입력 보존 여부까지 함께 보고 구현을 선택해야 한다.