파이썬으로 2차원 행렬 요소를 나선형 순서로 출력하는 프로그램

2차원 행렬 mat이 주어졌을 때, 이 행렬의 요소들을 나선형(spiral) 형태로 출력하는 문제를 생각해 볼 수 있습니다. 먼저 첫 번째 행(mat[0][0])부터 시작하여 해당 행 전체를 출력하고, 이어서 마지막 열을 따라 내려간 후, 다시 마지막 행을 거꾸로 지나가고, 그다음 첫 번째 열을 위로 올라가는 식으로 안쪽으로 나선을 그리며 요소를 차례대로 출력합니다.

예를 들어 다음과 같은 행렬이 입력으로 주어졌다고 가정해 보겠습니다.

그렇다면 출력 결과는 다음과 같습니다.

[7, 10, 9, 1, 3, 4, 5, 11, 9, 9, 2, 9, 6, 2, 9, 2, 1, 7]

해결 접근 방식

이 문제는 경계(top, bottom, left, right)를 점점 좁혀 가면서 네 방향으로 순회하는 방식으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.

• d := 0 으로 초기화합니다.
• top := 0, down := 행 개수 − 1, left := 0, right := 열 개수 − 1 로 경계를 설정합니다.
• c := 0 으로 초기화합니다.
• res := 결과를 저장할 새 리스트를 만듭니다.
• direction := 0 (순회 방향 인덱스)으로 초기화합니다.
• top <= down 이고 left <= right 인 동안 반복합니다.
  • direction == 0 (왼쪽 → 오른쪽): top 행의 요소를 left부터 right까지 res에 추가한 뒤, top을 1 증가시킵니다.
  • direction == 1 (위 → 아래): right 열의 요소를 top부터 down까지 res에 추가한 뒤, right를 1 감소시킵니다.
  • direction == 2 (오른쪽 → 왼쪽): down 행의 요소를 right부터 left까지 역순으로 res에 추가한 뒤, down을 1 감소시킵니다.
  • direction == 3 (아래 → 위): left 열의 요소를 down부터 top까지 역순으로 res에 추가한 뒤, left를 1 증가시킵니다.
• direction := (direction + 1) mod 4 로 방향을 갱신합니다.
• 모든 순회가 끝나면 res를 반환합니다.

예제 코드

다음 구현을 통해 더 자세히 이해해 보겠습니다.

Python 코드

class Solution:
   def solve(self, matrix):
      d = 0
      top = 0
      down = len(matrix) - 1
      left = 0
      right = len(matrix[0]) - 1
      c = 0
      res = []
      direction = 0
      while top <= down and left <= right:
         if direction == 0:
            for i in range(left, right + 1):
               res.append(matrix[top][i])
            top += 1

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

         if direction == 2:
            for i in range(right, left - 1, -1):
               res.append(matrix[down][i])
            down -= 1

         if direction == 3:
            for i in range(down, top - 1, -1):
               res.append(matrix[i][left])
            left += 1

         direction = (direction + 1) % 4
      return res

ob = Solution()
matrix = [
   [7, 10, 9],
   [2, 9, 1],
   [6, 2, 3],
   [9, 1, 4],
   [2, 7, 5],
   [9, 9, 11]
]
print(ob.solve(matrix))

입력

[
   [7, 10, 9],
   [2, 9, 1],
   [6, 2, 3],
   [9, 1, 4],
   [2, 7, 5],
   [9, 9, 11]
]

출력

[7, 10, 9, 1, 3, 4, 5, 11, 9, 9, 2, 9, 6, 2, 9, 2, 1, 7]

동작 원리 정리

이 알고리즘은 각 방향마다 한 겹(레이어)씩 순회하면서 해당 경계를 안쪽으로 좁혀 나갑니다. 예제 입력 기준으로 동작 과정을 보면 다음과 같습니다.

1. 첫 번째 행인 7, 10, 9를 순서대로 추가합니다.
2. 마지막 열을 아래로 내려가며 1, 3, 4, 5, 11을 추가합니다.
3. 마지막 행을 오른쪽에서 왼쪽으로 지나가며 9, 9, 2, 9를 추가합니다.
4. 첫 번째 열을 아래에서 위로 올라가며 6, 2, 9, 2를 추가합니다.
5. 남은 내부 영역에 대해 같은 과정을 반복하여 1, 7을 추가합니다.

이처럼 경계 변수를 활용한 네 방향 순회 방식은 시간 복잡도 O(m×n)(m은 행 개수, n은 열 개수), 공간 복잡도는 결과 저장을 제외하면 O(1)로 매우 효율적입니다. 행렬이 비어 있는 경우에도 while 조건에서 바로 종료되므로 안전하게 처리됩니다.