[Leetcode/파이썬] 54. Spiral Matrix

Spiral Matrix

---

Given an m x n matrix, return all elements of the matrix in spiral order.

 

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

 

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        n, m = len(matrix), len(matrix[0])
        board = copy.deepcopy(matrix)

        di = [0, 1, 0, -1]
        dj = [1, 0, -1, 0]

        d = 0
        res = []
        ci, cj = 0, 0
        res.append(matrix[0][0])
        board[0][0] = '.'
        while len(res) != n * m :
            if 0 <= ci + di[d] < n and 0 <= cj + dj[d] < m and\
                board[ci + di[d]][cj + dj[d]] != '.' :
                res.append(board[ci+di[d]][cj+dj[d]])
                board[ci+di[d]][cj+dj[d]] = '.'
                ci = ci+di[d]
                cj = cj+dj[d]
                
            else :
                d = (d+1)%4

        return res

첫 번째 풀이는 말 그대로 우, 하, 좌, 상 방향으로 진행하면서 방문했던 board 판에는 '.'으로 방문 처리를 함으로써, 재방문 하지 않고 그대로 진행하는 방식이다. 우리가 DFS나 BFS를 처리할 때 많이 했던 방문 처리와 유사한 방식으로 방문 처리를 진행하였다. 

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

        while len(res) < rows * cols :
            for i in range(left, right + 1) :
                res.append(matrix[top][i])
            top += 1

            for i in range(top, bottom + 1) :
                res.append(matrix[i][right])
            right -= 1

            if top <= bottom :
                for i in range(right, left - 1, -1) :
                    res.append(matrix[bottom][i])
                bottom -= 1

            if left <= right :
                for i in range(bottom, top - 1, -1) :
                    res.append(matrix[i][left])
                left += 1
        return res

그리고 두 번째 방법은 경계를 계속해서 좁혀가면서 진행하는 것이다. 

1. 오른쪽을 다 진행하면 상단 경계를 +1 만큼 옮긴다.
2. 아래 방향의 진행이 모두 완료되면 우측 경계를 -1 만큼 옮긴다. 
3. 왼쪽을 다 진행하면 하단 경계를 -1 만큼 옮긴다.
4. 윗 방향을 다 진행하면 좌측 경계를 +1 만큼 옮긴다. 

여기서 if 조건문을 시행하지 않게 되면 while 문이 한 번 더 진행되기 때문에 문제의 조건과 맞지 않게 된다. 

오랜만에 푸니까 잘 못 풀었다. 경계값을 하나씩 줄여가는 방식으로 처음에 도전했다가 예전에 풀었던 다른 문제를 한 번 살펴보고 응용해서 풀었다. (이게 첫 번째 코드) 

방문 처리가 확실히 쉬운 방법이기는 하나, 문제에서 요구하는 방법일지에 대해서는 한 번 고려할 필요가 있다.