이 문제에서는 2차원 행렬이 주어지며, 우리의 목표는 행렬의 모든 요소를 역 나선(reverse spiral) 형태로 출력하는 것입니다.
문제 이해하기
먼저 예시를 통해 문제를 살펴보겠습니다.
입력:
12 23 54 67
76 90 01 51
43 18 49 5
31 91 75 9
출력: 18 49 1 90 76 43 31 91 75 9 5 51 67 54 23 12
출력 결과를 보면 행렬의 중앙에 있는 요소부터 시작해 나선 방향으로 바깥쪽으로 확장하며 요소를 읽어낸 것을 확인할 수 있습니다. 즉, 일반적인 나선형 순회와 정반대 순서로 요소를 출력해야 합니다.
접근 방법
역 나선 형태로 출력하는 가장 간단하고 효율적인 방법은 다음 두 단계로 구성됩니다.
- 행렬을 일반적인 나선형(spiral) 순서로 순회하면서 모든 요소를 임시 배열에 저장합니다.
- 배열에 저장된 요소를 마지막 인덱스부터 첫 번째 인덱스까지 거꾸로 출력합니다.
나선형 순회는 네 개의 반복문을 사용해 구현할 수 있습니다. 각 반복문은 위쪽 행 → 오른쪽 열 → 아래쪽 행 → 왼쪽 열을 차례로 처리하며, 한 바퀴를 돌 때마다 경계 변수(k, l, m, n)를 안쪽으로 좁혀 나갑니다. 이렇게 수집한 요소들을 역순으로 출력하면 중앙에서 시작하는 역 나선 형태가 자연스럽게 만들어집니다.
C++ 구현 예제
다음은 위 접근 방식을 구현한 프로그램입니다.
#include <iostream>
#define R 3
#define C 6
using namespace std;
void printReverseSpiral(int m, int n, int a[R][C]) {
long int b[100];
int i, k = 0, l = 0;
int z = 0;
int size = m*n;
while (k < m && l < n) {
int val;
// 위쪽 행을 왼쪽에서 오른쪽으로
for (i = l; i < n; ++i){
val = a[k][i];
b[z] = val;
++z;
}
k++;
// 오른쪽 열을 위에서 아래로
for (i = k; i < m; ++i){
val = a[i][n-1];
b[z] = val;
++z;
}
n--;
// 아래쪽 행을 오른쪽에서 왼쪽으로
if ( k < m){
for (i = n-1; i >= l; --i){
val = a[m-1][i];
b[z] = val;
++z;
}
m--;
}
// 왼쪽 열을 아래에서 위로
if (l < n){
for (i = m-1; i >= k; --i){
val = a[i][l];
b[z] = val;
++z;
}
l++;
}
}
// 저장된 요소를 역순으로 출력
for (int i=size-1 ; i>=0 ; --i){
cout<<b[i]<<" ";
}
}
int main() {
int mat[R][C] = {
{34, 5, 6, 98, 12, 23},
{9, 12, 56, 87, 99, 1},
{13, 91, 50, 8, 21, 2}
};
cout<<"Printing reverse Spiral of the matrix :\n";
printReverseSpiral(R, C, mat);
return 0;
}
실행 결과
Printing reverse Spiral of the matrix −
99 87 56 12 9 13 91 50 8 21 2 1 23 12 98 6 5 34
코드 설명
위 코드에서 k와 l은 아직 순회하지 않은 영역의 시작 행과 시작 열을, m과 n은 끝 행과 끝 열을 나타냅니다. while 루프 안의 네 개의 for 문이 각각 나선의 한 변씩을 담당하며, 각 변을 처리한 후에는 해당 경계 값을 조정해 순회 범위를 한 겹씩 줄여 나갑니다.
모든 요소가 배열 b에 나선 순서로 저장되면, 마지막 반복문이 이를 뒤에서부터 앞으로 출력합니다. 그 결과 행렬의 중앙 요소부터 시작해 바깥쪽으로 나선을 그리듯 확장하는 역 나선 출력이 완성됩니다.
이 알고리즘의 시간 복잡도는 행렬의 모든 요소를 한 번씩 방문하므로 O(m×n)이며, 추가 공간 복잡도 역시 요소를 저장하기 위한 배열 크기만큼인 O(m×n)입니다.