[Leetcode 아주 상세한 문제풀이] 54. Spiral Matrix – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 54번 문제 Spiral Matrix 다.

우선 문제를 살펴보자.

 

리트코드 54번 문제 Spiral Matrix 링크

https://leetcode.com/problems/spiral-matrix/

Spiral Matrix - LeetCode

 

 

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

 

 

문제 설명

문제를 간략히 살펴보자. 인풋으로 사이즈가 m * n인 매트릭스가 주어진다. 이때 모든 element를 지나가야 하는데 spirla order로 지나야 한다. 즉, 매트릭스의 가장 위 왼쪽 코너에서 시작해 시계 방향으로 바깥쪽부터 안쪽으로 모든 element를 지나야 한다. 이때 모든 element를 지나는 순서를 차례대로 나타내라는 것이다.

문제 예시 1번을 살펴보면 1부터 9까지 3*3 매트릭스에 순서대로 배열이 되어있다. 이 경우 매트릭스의 가장 위 왼쪽 1에서 시작해 시계 방향으로 이동하여 최종적으로 5에 도달할 수 있다. 이때 각 element를 지나는 순서는 1->2->3->6->9->8->7->7->4->5가 된다. 따라서 이 순서대로 [1, 2, 3, 6, 9, 8, 7, 4, 5] 배열을 리턴하면 된다. 문제를 이해하기 어렵지 않으니 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제를 해결하기 위해서는 spiral order에 대한 정확한 이해가 필요하다.

이 문제에서 정의하고 있는 spiral order는 결국 모든 element를 오른쪽->아래->왼쪽->위 순서대로 탐색하라는 것이다.

이때 우리는 위/아래/좌/우 가장자리를 계속 업데이트 해야 한다.

즉, 탐색을 정해진 순서대로 계속하되 4가지 경우 중 한 가지 경우의 탐색을 마치고 나면 그 가장자리를 업데이트 해야 한다.

구체적으로 다음과 같이 탐색이 진행된다.

 

1) 가장 윗 열을 왼쪽에서 오른쪽 순으로 탐색을 한다. 탐색을 마치면 위 가장자리를 아래로 하나 옮겨준다.

2) 가장 오른쪽 행을 위에서 아래 순으로 탐색을 한다. 탐색을 마치면 오른쪽 가장자리를 왼쪽으로 하나 옮겨준다.

3) 가장 아래쪽 행을 오른쪽에서 왼쪽 순으로 탐색을 한다. 탐색을 마치면 아래쪽 가장자리를 위쪽으로 하나 옮겨준다.

4) 가장 왼쪽 행을 아래에서 위 순으로 탐색을 한다. 탐색을 마치면 왼쪽 가장자리를 오른쪽으로 하나 옮겨준다.

이 과정을 계속 반복해주는데 이때 왼쪽 가장자리와 오른쪽 가장자리가 서로 만나거나 혹은 왼쪽 가장자리와 아래쪽 가장자리가 서로 만나지 않는 이상 탐색을 계속한다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

매트릭스를 구성하는 배열을 입력받을 함수를 정의해 준다. (line 1)

만약 함수가 비어있다면 빈 리스트를 리턴하고 종료한다. (line 2-3)

결과값을 저장할 빈 리스트를 하나 만들어 준다. (line 5)

이제 가장자리를 세팅해 주는데 왼쪽과 오른쪽 가장자리는 매트릭스의 왼쪽과 오른쪽 끝으로 세팅한다. (line 6)

그리고 위 아래 가장자리는 매트릭스의 가장 위와 가장 아래쪽 끝으로 세팅한다. (line 7)

이제 왼쪽과 오른쪽 가장자리가 만나지 않고 위쪽 가장자리와 아래쪽 가장자리가 만나지 않는 동안 탐색을 계속한다. (line 9)

첫번째로 가장 첫번째 행을 왼쪽에서 오른쪽으로 탐색하여 차례대로 결과 리스트에 넣는다. (line 11-12)

탐색을 마치면 위쪽 가장자리를 아래로 한 칸 옮겨준다. (line 13)

두번째로 가장 오른쪽 열을 위에서 아래로 탐색하여 차례대로 결과 리스트에 넣는다. (line 16-17)

탐색을 마치면 오른쪽 가장자리를 왼쪽으로 한 칸 옮겨준다. (line 18)

이때 가장 첫번째 행과 가장 오른쪽 열을 탐색하고 나면 그 둘을 더 이상 탐색이 필요하지 않다.

즉, 그 둘을 제외한 더 작은 매트릭스에서 탐색이 시작된다.

따라서 왼쪽 가장자리와 오른쪽 가장자리가 만나지 않았는지, 그리고 위쪽 가장자리와 아래쪽 가장자리가 만나지 않았는지 확인하고 혹시 만났다면 탐색을 종료한다. (line 20-21)

세번째로 가장 아래쪽 행을 오른쪽에서 왼쪽으로 탐색하여 차례대로 결과 리스트에 넣는다. (line 24-25)

탐색을 마치면 아래쪽 가장자리를 로 한 칸 옮겨준다. (line 36)

마지막으로 가장 왼쪽 열을 아래에서 위로 탐색하여 차례대로 결과 리스트에 넣는다. (line 29-30)

탐색을 마치면 왼쪽 가장자리를 오른쪽으로 한 칸 옮겨준다. (line 31)

이 모든 과정을 마치고 나면 spiral order로 탐색된 element가 결과 리스트에 저장되어 있다.

그 결과 리스트를 리턴하고 종료한다. (line 33)

 

 

문제 풀이 코드

def spiralOrder(matrix):
    if not matrix:
        return []
 
    result = []
    left, right = 0, len(matrix[0])
    top, bottom = 0, len(matrix)
 
    while left < right and top < bottom:
        # Get every i in the top row
        for i in range(left, right):
            result.append(matrix[top][i])
        top += 1
 
        # Get every i in the right column
        for i in range(top, bottom):
            result.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):
            result.append(matrix[bottom - 1][i])
        bottom -= 1
 
        # Get every i in the left column
        for i in range(bottom - 1, top - 1, -1):
            result.append(matrix[i][left])
        left += 1
 
    return result
 
# Test the function with the provided examples
matrix1 = [[1,2,3],[4,5,6],[7,8,9]]
print(spiralOrder(matrix1))  # Output: [1,2,3,6,9,8,7,4,5]
 
matrix2 = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
print(spiralOrder(matrix2))  # Output: [1,2,3,4,8,12,11,10,9,5,6,7]
 

 

관련 문제

리트코드 48번 Rotate image 문제 풀이 (링크)

리트코드 73번 Set matrix zeroes 문제 풀이 (링크)

리트코드 79번 Word search 문제 풀이 (링크)

 

54. Spiral Matrix