스택을 활용해 행렬을 안티스파이럴(역나선) 순서로 출력하기

n×n 크기의 2차원 배열이 주어졌을 때, 해당 행렬을 안티스파이럴(anti-spiral, 역나선) 형태로 배치하여 출력하는 것이 이 글의 목표입니다. 안티스파이럴이란 일반적인 나선 순회의 정반대 순서로, 행렬의 가장 안쪽 원소부터 바깥쪽 테두리 방향으로 나선형을 거꾸로 그려 나가는 것을 의미합니다.

문제 예시

입력 : arr[4][4] = { 1,  2,  3,  4,
                     5,  6,  7,  8,
                     9, 10, 11, 12,
                    13, 14, 15, 16 }

출력 : 10 11 7 6 5 9 13 14 15 16 12 8 4 3 2 1

출력 결과를 보면 먼저 내부 2×2 영역(6, 7, 11, 10)이 역방향으로 출력되고, 이후 바깥쪽 테두리가 역나선 방향으로 이어지는 것을 확인할 수 있습니다.

접근 방식: 스택(Stack) 활용

핵심 아이디어는 의외로 간단합니다. 행렬을 일반적인 나선(spiral) 순서로 순회하면서 각 원소를 스택에 push하고, 모든 원소를 담은 뒤 스택에서 하나씩 pop하며 출력하면 됩니다.

스택은 LIFO(Last-In, First-Out) 구조이므로, 나선 순회의 맨 마지막 원소(행렬 중앙부)가 가장 먼저 출력됩니다. 결국 전체 나선 순회 결과가 뒤집혀 출력되며, 이것이 바로 안티스파이럴 배열이 됩니다.

알고리즘

START
STEP 1 -> 스택 stk를 선언하고 변수 r=4, c=4, i, j, rs=0, cs=0 초기화
STEP 2 -> 행렬 원소를 2차원 배열에 저장
STEP 3 -> Loop For i=0 ~ i<4, i++
   Loop For j=0 ~ j<4, j++
      arr[i][j] 출력
   줄바꿈(\n) 출력
STEP 4 -> Loop While(rs<c && cs<r)
   Loop For i=rs ~ i<c, i++
      arr[rs][i]를 스택에 push
   cs++
   Loop For i=cs ~ i<r-1, ++i
      arr[i][c-1]을 스택에 push
   c--
   IF(cs<r)
      Loop For i=r-1 ~ i>=rs, --i
         arr[r-1][i]를 스택에 push
      r--
   IF(rs<c)
      Loop For i=c-1 ~ i>=cs, i--
         arr[i][rs]를 스택에 push
      rs++
STEP 5 -> Loop While(!stk.empty())
   stk.top() 출력
   pop() 호출
STOP

C++ 예제 코드

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> stk;
    int R = 4, C = 4, i, j, RS = 0, CS = 0;
    int mat[4][4] = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16} };

    // 입력 행렬 출력
    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4; j++)
            cout << mat[i][j] << " ";
        cout << "\n";
    }

    // 나선 순서로 순회하며 스택에 push
    while (RS < C && CS < R) {
        for (i = RS; i < C; i++)           // 위쪽 행: 왼쪽 → 오른쪽
            stk.push(mat[RS][i]);
        CS++;
        for (i = CS; i < R - 1; ++i)       // 오른쪽 열: 위 → 아래
            stk.push(mat[i][C - 1]);
        C--;
        if (CS < R) {
            for (i = R - 1; i >= RS; --i)  // 아래쪽 행: 오른쪽 → 왼쪽
                stk.push(mat[R - 1][i]);
            R--;
        }
        if (RS < C) {
            for (i = C - 1; i >= CS; i--)  // 왼쪽 열: 아래 → 위
                stk.push(mat[i][RS]);
            RS++;
        }
    }

    // 스택에서 pop하며 역나선 순서로 출력
    while (!stk.empty()) {
        cout << stk.top() << " ";
        stk.pop();
    }
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

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

복잡도 분석

행렬의 모든 원소를 한 번씩 방문하므로 시간 복잡도는 O(n²), 모든 원소를 스택에 저장하므로 공간 복잡도 역시 O(n²)입니다. 추가적인 역순 회전 연산 없이 스택의 LIFO 특성만으로 안티스파이럴 출력을 얻을 수 있다는 점이 이 접근 방식의 가장 큰 장점입니다.