C++로 나선형 행렬(Spiral Matrix) 출력하기

나선형 행렬(Spiral Matrix)이란?

행렬이 주어졌을 때 모든 요소를 나선형(spiral) 순서로 출력해야 하는 경우가 있습니다. 먼저 첫 번째 행의 전체 내용을 출력한 뒤, 마지막 열을 따라 위에서 아래로 출력하고, 이어서 마지막 행을 오른쪽에서 왼쪽으로, 그다음에는 첫 번째 열을 아래에서 위로 출력합니다. 한 바퀴를 돌고 나면 경계를 한 단계씩 안쪽으로 좁혀 가며 같은 과정을 반복하는 방식입니다.

예를 들어 다음과 같은 3×6 행렬이 있다고 가정해 보겠습니다.

이 행렬을 나선형으로 출력하면 결과는 다음과 같습니다.

[1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11]

문제 해결 접근 방법

핵심은 네 개의 경계, 즉 첫 행·마지막 열·마지막 행·첫 열을 변수로 관리하면서 레이어(layer) 단위로 출력하는 것입니다. 구체적인 단계는 다음과 같습니다.

• currRow := 0, currCol := 0으로 초기화합니다.
• currRow와 currCol이 행렬 범위 내에 있는 동안 다음 과정을 반복합니다.
  • i를 currCol부터 n-1까지 이동시키며 mat[currRow][i]를 출력합니다. (첫 번째 행)
  • currRow를 1 증가시킵니다.
  • i를 currRow부터 m-1까지 이동시키며 mat[i][n-1]을 출력합니다. (마지막 열)
  • n을 1 감소시켜 새로운 마지막 열을 지정합니다.
  • currRow < m이라면, i를 n-1부터 currCol까지 감소시키며 mat[m-1][i]를 출력합니다. (마지막 행) 이후 m을 1 감소시킵니다.
  • currCol < n이라면, i를 m-1부터 currRow까지 감소시키며 mat[i][currCol]을 출력합니다. (첫 번째 열) 이후 currCol을 1 증가시킵니다.

C++ 구현 예제

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

#include <iostream>
#define ROW 3
#define COL 6
using namespace std;
int array[ROW][COL] = {{1, 2, 3, 4, 5, 6},
   {7, 8, 9, 10, 11, 12},
   {13, 14, 15, 16, 17, 18}};
void dispSpiral(int m, int n){
   int i, currRow = 0, currCol = 0;
   while (currRow < ROW && currCol < COL){
      for (i = currCol; i < n; i++){ //첫 번째 행을 그대로 출력
         cout << array[currRow][i]<<" ";
      }
      currRow++; //다음 행으로 이동
      for (i = currRow; i < m; ++i){ //마지막 열 출력
         cout << array[i][n-1]<<" ";
      }
      n--; //n-1번째 열을 새로운 마지막 열로 설정
      if ( currRow < m){ //currRow가 범위 내에 있으면 마지막 행 출력
         for (i = n-1; i >= currCol; --i){
            cout << array[m-1][i]<<" ";
         }
         m--; //행 범위 축소
      }
      if (currCol < n){ //currCol이 범위 내에 있으면 첫 번째 열 출력
         for (i = m-1; i >= currRow; --i){
            cout << array[i][currCol]<<" ";
         }
         currCol++;
      }
   }
}
int main(){
   dispSpiral(ROW, COL);
}

입력

[[1,2,3,4,5,6]
[7,8,9,10,11,12]
[13,14,15,16,17,18]]

출력

1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11

시간 및 공간 복잡도

이 알고리즘은 행렬의 각 요소를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(m×n)입니다. 또한 경계를 추적하는 변수 몇 개만 사용할 뿐 추가적인 저장 공간이 필요하지 않으므로 공간 복잡도는 O(1)입니다.