[LeetCode]Spiral Matrix

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

Spiral Matrix - LeetCode

 

문제 분석

주어진 Grid를 시계 방향으로 달팽이 회전하듯이 탐색할 때 그 경로를 기록하는 문제입니다.

 

처음 시도한 답안

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

        row_begin = 0
        col_begin = 0
        row_end = len(matrix)-1 
        col_end = len(matrix[0])-1

        while row_begin <= row_end and col_begin <= col_end:
            # col 값이 증가하면서 오른쪽 방향으로 탐색
            for i in range(col_begin, col_end+1):
                answer.append(matrix[row_begin][i])
            # 가장 위의 row들을 탐색했으니 row 시작 지점을 1 증가
            row_begin += 1
            
            # row 값이 증가하면서 아래쪽 방향으로 탐색
            for j in range(row_begin, row_end+1):
                answer.append(matrix[j][col_end])
            # 가장 오른쪽의 col들을 탐색했으니 col 끝 지점을 1 감소
            col_end -= 1

            # row 시작 <= row 끝인 경우에만 왼쪽 방향으로 탐색
            if row_begin <= row_end:
                for x in range(col_end, col_begin-1, -1):
                    answer.append(matrix[row_end][x])
                # 가장 아래의 row들을 탐색했으니 row 끝 지점을 1 감소
                row_end -= 1

            # col 시작 <= col 끝인 경우에만 위쪽 방향으로 탐색 
            if col_begin <= col_end:
                for k in range(row_end, row_begin-1, -1):
                    answer.append(matrix[k][col_begin])
                # 가장 왼쪽의 col들을 탐색했으니 col 시작 지점을 1 증가
                col_begin += 1
                
        return answer

접근 방법

1. row와 col의 시작과 끝 포인트를 변수로 할당합니다.
2. row_begin <= row_end && col_begin <= col_end 동안 반복합니다.
3. 가장 위의 row의 숫자를 탐색하기 위해 col의 수만큼 반복합니다. (오른쪽 방향 탐색)
4. 가장 위의 row 탐색이 완료 되었으므로 row_begin 시작 지점을 1 증가시킵니다.
5. 가장 오른쪽의 col의 숫자를 탐색하기 위해 row의 수만큼 반복합니다. (아래 방향으로 탐색)
6. 가장 오른쪽의 col 탐색이 완료 되었으므로 col_end 지점을 1 감소시킵니다.
7. row_begin <= row_end인 경우에만 가장 아래쪽 row를 탐색합니다. (왼쪽 방향 탐색)
8. 가장 아래의 row 탐색이 완료 되었으므로 row_end 지점을 1 감소시킵니다.
9. col_begin <= col_end인 경우에만 가장 왼쪽 col들을 탐색합니다. (위쪽 방향 탐색)
10. 가장 왼쪽의 col 탐색이 완료 되었으므로 col_begin 지점을 1 증가합니다.

탐색하는 지점을 기록하면서 오른 -> 아래 -> 왼 -> 위 순서대로 계속해서 반복 탐색하는 방식입니다.

그 중에서도 오른쪽과 아래는 별다른 조건이 없지만 왼쪽과 위 방향의 경우는 begin이 end보다 같거나 작은 경우에만 가능합니다.

 

문제의 그림을 함께 참고하면서 반복을 따라가다보면 쉽게 이해할 수 있습니다. 탐색한 row, col들을 아예 없는 것으로 취급한다고 생각하면 됩니다.