LeetCode 54(Spiral Matrix, Python)

1. 문제 링크

• Spiral Matrix - LeetCode

Spiral Matrix - LeetCode

2. 문제 설명

• m×n 행렬이 주어졌을 때, 왼쪽 위에서 시작해서 회오리 돌며 진행하며 수를 리스트에 넣어 반환
• 예시) matrix = [[1,2,3],[4,5,6],[7,8,9]] → [1,2,3,6,9,8,7,4,5] 반환

3. 처음 풀이

• 사람이 있는 방에 상하좌우 벽을 세워두고 이동하다가 상하좌우 벽에 도착하면 도착한 벽을 안쪽으로 한 칸 옮기고, 이동 방향 조정해주기. 이때 위로 올라오며 가장 처음 만나는 벽은 1이 아니라 4이므로 위쪽 벽은 0이 아닌 1로 둔다. (right = 2, down = 2, left = 0, up = 1)
• 1에서 출발해서 오른쪽으로 이동하다가(1→2→3), 오른쪽 벽에 닿으면(369), 이동 방향을 아래로 바꾸고, 오른쪽 벽을 왼쪽으로 한 칸 조정(258)
• 3에서 아래로 이동하다가(3→6→9), 아래쪽 벽에 닿으면(789), 이동 방향을 왼쪽으로 바꾸고, 아래쪽 벽을 위로 한 칸 조정(456)
• 9에서 왼쪽으로 이동하다가(987), 왼쪽 벽에 닿으면(147), 이동 방향을 위쪽으로 바꾸고, 왼쪽 벽을 오른쪽으로 한 칸 조정(258)
• 7에서 위로 이동하다가(7→4), 위쪽 벽에 닿으면(456), 이동 방향을 오른쪽으로 바꾸고, 위쪽 벽을 아래로 한 칸 조정(789)
• 4에서 오른쪽으로 이동하다가(4→5), 오른쪽 벽에 닿았고(258), 3*3 번 수행했으므로 반복문 종료.

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        result = []
        x, y, delta_x, delta_y = 0, 0, 1, 0 #position and direction of movement
        cnt = len(matrix)*len(matrix[0]) #size of matrix
        left, right, up, down = 0, len(matrix[0])-1, 1, len(matrix)-1 #boundary

        for _ in range(cnt):
            if delta_x == 1 and x == right: #reaching right end
                right -= 1
                delta_x, delta_y = 0, 1
            elif delta_y == 1 and y == down: #reaching bottom end
                down -= 1
                delta_x, delta_y = -1, 0
            elif delta_x == -1 and x == left: #reaching left end
                left += 1
                delta_x, delta_y = 0, -1
            elif delta_y == -1 and y == up: #reaching top end
                up += 1
                delta_x, delta_y = 1, 0
            result.append(matrix[y][x])
            x += delta_x
            y += delta_y

        return result

4. 다른 풀이

• 나는 점이 이동한다고 생각하였고, 한 줄씩 접근해도 된다. 물론 대동소이

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

        while (top < bottom and left < right):
            #get every i in the top row 
            for i in range(left, right):
                res.append(matrix[top][i])
            top += 1

            #get every i in the right coloum 
            for i in range(top,bottom):
                res.append(matrix[i][right-1])
            right -= 1

            if not (left < right and top < bottom):
                break

            #get every i in the bottom row 
            for i in range(right-1,left-1, -1):
                res.append(matrix[bottom-1][i])
            bottom -= 1

            #get every i in the left coloum 
            for i in range(bottom-1, top-1, -1):
                res.append(matrix[i][left])
            left += 1

        return res

5. 배운 점

• 현재 위치와 위치 변화량을 따로 변수에 저장해두고 관리하는게 편리한 경우가 있다.