Spiral Matrix

LeetCode의 33번째 문제인 Spiral Matrix를 함께 풀어보도록 하겠습니다.

문제

m x n 행렬이 주어졌을 때, 행렬의 모든 요소를 나선형 순서로 반환하시오.

예제

입력: matrix = [[1,2,3],[4,5,6],[7,8,9]]
출력: [1,2,3,6,9,8,7,4,5]

입력: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
출력: [1,2,3,4,8,12,11,10,9,5,6,7]

풀이 1

나선형 순서로 요소에 접근하려면 양파 껍질을 벗기듯이 바깥쪽에서 안쪽으로 행렬을 순회해야 하는데요.

예를 들어, 7 x 5 행렬을 나선형 순서로 순회하면 다음과 같은 모습이 될 것입니다.

👉👉👉👉👉    👉👉👉👉👉    👉👉👉👉👉    👉👉👉👉👉
🟩🟩🟩🟩👇    🟩🟩🟩🟩👇    🟩🟩🟩🟩👇    👆🟩🟩🟩👇
🟩🟩🟩🟩👇    🟩🟩🟩🟩👇    🟩🟩🟩🟩👇    👆🟩🟩🟩👇
🟩🟩🟩🟩👇    🟩🟩🟩🟩👇    🟩🟩🟩🟩👇    👆🟩🟩🟩👇
🟩🟩🟩🟩👇    🟩🟩🟩🟩👇    🟩🟩🟩🟩👇    👆🟩🟩🟩👇
🟩🟩🟩🟩👇    🟩🟩🟩🟩👇    🟩🟩🟩🟩👇    👆🟩🟩🟩👇
🟩🟩🟩🟩👈    🟩🟩🟩🟩👇    👈👈👈👈👇    👈👈👈👈👇

👉👉👉👉👉    👉👉👉👉👉    👉👉👉👉👉    👉👉👉👉👉
👆👉👉👉👇    👆👉👉👉👇    👆👉👉👉👇    👆👉👉👉👇
👆🟩🟩🟩👇    👆🟩🟩👇👇    👆🟩🟩👇👇    👆👆🟩👇👇
👆🟩🟩🟩👇    👆🟩🟩👇👇    👆🟩🟩👇👇    👆👆🟩👇👇
👆🟩🟩🟩👇    👆🟩🟩👇👇    👆🟩🟩👇👇    👆👆🟩👇👇
👆🟩🟩🟩👇    👆🟩🟩👇👇    👆👈👈👇👇    👆👈👈👇👇
👈👈👈👈👇    👈👈👈👈👇    👈👈👈👈👇    👈👈👈👈👇

👉👉👉👉👉    👉👉👉👉👉
👆👉👉👉👇    👆👉👉👉👇
👆👆👉👇👇    👆👆👉👇👇
👆👆🟩👇👇    👆👆👇👇👇
👆👆🟩👇👇    👆👆👇👇👇
👆👈👈👇👇    👆👈👈👇👇
👈👈👈👈👇    👈👈👈👈👇

위 과정을 관찰해보시면 일정한 패턴이 보이실텐데요. 남은 영역의 가장 바깥 쪽을 순회하는데, 위쪽 행, 오른쪽 열, 아래쪽 행, 왼쪽 열 순으로 순회를 합니다. 그리고 순회를 하면 할 수록 남은 영역이 사각형 형태로 계속 줄어듭니다.

따라서 우리는 순회 범위를 좁혀 나가기 위해서 4개의 포인터가 필요합니다. 행(높이) 기준으로 상하단 경계의 인덱스와 열(너비) 기준으로 좌우측 경계의 인덱스를 기억하기 위함입니다. 그리고 포인터의 값은 순회가 진행됨에 따라 다음과 같은 로직으로 변경할 수 있습니다.

• 위쪽 행을 순회한 후, 상단 경계를 1 증가
• 우측 열을 순회한 후, 우측 경계를 1 감소
• 아래쪽 행을 순회한 후, 하단 경계를 1 감소
• 왼쪽 행을 순회한 후, 좌측 경계를 1 증가

문제의 첫 번째 예제에서 주어진 행렬을 상대로 이 알고리즘을 적용해보겠습니다.

1️⃣2️⃣3️⃣
4️⃣5️⃣6️⃣
7️⃣8️⃣9️⃣

결과: []
상: 0, 우: 2, 하: 2, 좌: 0

👉👉👉
4️⃣5️⃣6️⃣
7️⃣8️⃣9️⃣

결과: [] + [1, 2, 3]
상: 0 + 1 = 1, 우: 2, 하: 2, 좌: 0

👉👉👉
4️⃣5️⃣👇
7️⃣8️⃣👇

결과: [1, 2, 3] + [6, 9]
상: 1, 우: 2 - 1 = 1, 하: 2, 좌: 0

👉👉👉
4️⃣5️⃣👇
👈👈👇

결과: [1, 2, 3, 6, 9] + [8, 7]
상: 1, 우: 1, 하: 2 - 1 = 1, 좌: 0

👉👉👉
👆5️⃣👇
👈👈👇

결과: [1, 2, 3, 6, 9, 8, 7] + [4]
상: 1, 우: 1, 하: 1, 좌: 0 + 1 = 1

👉👉👉
👆👉👇
👈👈👇

결과: [1, 2, 3, 6, 9, 8, 7, 4] + [3]
상: 1 + 1 = 2, 우: 1, 하: 1, 좌: 1

행렬에 있는 모든 원소를 결과 배열에 넣으면 상단 인덱스가 2로 하단 인덱스 1보다 오히려 커지는 것을 볼 수 있습니다. 따라서 우리는 상단 인덱스가 하단 인덱스보다 커지면 반복을 멈춰야 한다는 것을 알 수 있습니다.

그런데 만약에 입력 행렬의 높이가 더 높았다면 우측 인덱스가 0으로 좌측 인덱스 1보다 작아졌을 것입니다.

👉👉👉
👆👉👇
👆👇👇
👈👈👇

상 1 -> 우 1 -> 하 3 -> 좌 1 -> 상 2 -> 우 0

그러므로 다음 두 가지 경우가 발생하면 순회를 마쳐야 합니다.

• 위쪽 행 순회를 마치고, 상단 인덱스가 하단 인덱스보다 커지면
• 오른쪽 열 순회를 마치고, 우측 인덱스가 좌측 인덱스보다 작아지면

지금까지 설명드린 알고리즘을 코드로 구현해보겠습니다.

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1

        output = []

        while top <= bottom and left <= right:
            # 위쪽 행 순회
            for c in range(left, right + 1):
                output.append(matrix[top][c])
            top += 1

            # 상단 인덱스가 하단 인덱스보다 커지면 순회 중단
            if top > bottom:
                break

            # 오른쪽 열 순회
            for r in range(top, bottom + 1):
                output.append(matrix[r][right])
            right -= 1

            # 우측 인덱스가 좌측 인덱스보다 작아지면 순회 중단
            if left > right:
                break

            # 아래쪽 행 순회
            for c in range(right, left - 1, -1):
                output.append(matrix[bottom][c])
            bottom -= 1

            # 왼쪽 열 순회
            for r in range(bottom, top - 1, -1):
                output.append(matrix[r][left])
            left += 1

        return output

이 풀이는 행렬에 저장된 모든 원소를 딱 한 번씩 접근하므로 O(m * n)의 시간 복잡도를 가지게 됩니다. 공간 복잡도는 결과 배열을 제외한다면 추가 메모리를 사용하지 않으므로 O(1)입니다.

풀이 2

문제의 요구 사항은 간단한데 반해서 이전 풀이의 코드는 좀 길고 복잡한 감이 있습니다. 아무래도 상하단 경계와 좌우측 경계를 저장하는데 포인터가 4개나 필요해서 그런 것 같은데요.

이번에는 2개의 포인터만 사용해서 현재의 위치, 즉 행 인덱스와 열 인덱스만 저장하면 어떨까요? 그러면 행렬을 순회하면서 인덱스의 값은 다음과 같이 바뀔 것입니다.

1. 위쪽 행을 순회 중에는 열 인덱스를 1씩 증가
2. 우측 열을 순회 중에는 행 인덱스를 1씩 증가
3. 아래쪽 행을 순회 중에는 열 인덱스를 1씩 감소
4. 좌측 행을 순회 중에는 행 인덱스를 1씩 감소

그런데 공통적으로 첫 번째와 두 번째 순회에는 인덱스가 증가하고, 세 번째와 네 번째 순회에는 인덱스가 감소를 합니다. 그래서 변수에 처음에 1을 저장해놓고, 첫 번째와 두 번째 순회가 끝나면 -1을 곱하고, 세 번째와 네 번째 순회가 끝나면 다시 -1을 곱하면 다시 원래 1로 돌아올 것입니다. 이런 식으로 1을 더해야하는지 빼야하는지를 관리할 수 있을 것입니다.

그럼 상하단 경계와 좌우측 경계를 모르는 상태에서 각 순회에서 인덱스를 몇 회 증가시키거나 감소시켜야 할까요? 바로 아직 순회를 해야하는 남은 행의 개수와 열의 개수를 관리하면 됩니다. 공통적으로 첫 번째와 세 번째 순회가 끝나면 행의 개수를 1 감소시킬 수 있고, 두 번째와 네 번째 순회가 끝나면 열의 개수를 1 감소시킬 수 있습니다.

문제의 첫 번째 예제에서 주어진 행렬을 상대로 이 알고리즘을 적용해보겠습니다.

현재 인덱스: (0, -1)
줄의 개수: 3, 열의 개수: 3

1️⃣2️⃣3️⃣
4️⃣5️⃣6️⃣
7️⃣8️⃣9️⃣

결과: []

현재 인덱스: (0, 0) -> (0, 1) -> (0, 2)
줄의 개수: 3 - 1 = 2, 열의 개수: 3

👉👉👉
4️⃣5️⃣6️⃣
7️⃣8️⃣9️⃣

결과: [] + [1, 2, 3]

현재 인덱스: (1, 2) -> (2, 2)
줄의 개수: 2, 열의 개수: 3 - 1 = 2

👉👉👉
4️⃣5️⃣👇
7️⃣8️⃣👇

결과: [1, 2, 3] + [6, 9]

현재 인덱스: (2, 1) -> (2, 0)
줄의 개수: 2 - 1 = 1, 열의 개수: 2

👉👉👉
4️⃣5️⃣👇
👈👈👇

결과: [1, 2, 3, 6, 9] + [8, 7]

현재 인덱스: (2, 0) -> (1, 0)
줄의 개수: 1, 열의 개수: 2 - 1 = 1

👉👉👉
👆5️⃣👇
👈👈👇

결과: [1, 2, 3, 6, 9, 8, 7] + [4]

현재 인덱스: (1, 1)
줄의 개수: 1 - 1 = 0, 열의 개수: 1

👉👉👉
👆👉👇
👈👈👇

결과: [1, 2, 3, 6, 9, 8, 7, 4] + [3]

지금까지 설명드린 알고리즘을 코드로 구현해보겠습니다.

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        n_rows, n_cols = len(matrix), len(matrix[0])
        row, col = 0, -1
        direction = 1

        output = []

        while 0 < n_rows and 0 < n_cols:
            for _ in range(n_cols):
                col += direction
                output.append(matrix[row][col])
            n_rows -= 1

            for _ in range(n_rows):
                row += direction
                output.append(matrix[row][col])
            n_cols -= 1

            direction *= -1

        return output

코드가 줄어들고 간단해졌지만 이 풀이의 시간 복잡도와 공간 복잡도는 이전 풀이의 유의미한 차이가 없습니다.