이 문제에서는 2차원 행렬이 주어지며, 우리의 목표는 행렬의 모든 요소를 시계 반대 방향 나선형(counterclockwise spiral) 순서로 출력하는 것입니다.
시계 반대 방향 나선형이란?
시계 반대 방향 나선형 탐색은 행렬의 왼쪽 위(첫 번째 행, 첫 번째 열)에서 시작하여 아래 → 오른쪽 → 위 → 왼쪽 순서로 방향을 바꿔가며, 외곽에서부터 안쪽으로 나선을 그리듯 이동하는 방식입니다.
예를 들어 다음과 같은 4×4 행렬이 있을 때,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
시계 반대 방향 나선형 탐색 결과는 다음과 같습니다.
1 5 9 13 14 15 16 12 8 4 3 2 6 10 11 7
문제 이해를 위한 예제
입력:
2 4 6
1 7 9
5 0 3
출력: 2 1 5 0 3 9 6 4 7왼쪽 위의 2에서 시작해 첫 번째 열을 따라 내려가고(2 → 1 → 5), 마지막 행을 따라 오른쪽으로 이동한 뒤(0 → 3), 마지막 열을 따라 위로 올라가고(9 → 6), 첫 번째 행을 따라 왼쪽으로 이동하며(4), 마지막으로 중앙의 7을 방문하는 순서입니다.
해결 접근 방법
이 문제는 네 개의 반복문을 사용하여 해결할 수 있습니다. 각 반복문은 하나의 방향을 담당하며, 한 바퀴를 돌 때마다 탐색 범위를 안쪽으로 좁혀 나갑니다.
- 아래쪽: 현재 가장 왼쪽 열을 위에서 아래로 순회
- 오른쪽: 현재 가장 아래 행을 왼쪽에서 오른쪽으로 순회
- 위쪽: 현재 가장 오른쪽 열을 아래에서 위로 순회
- 왼쪽: 현재 가장 위 행을 오른쪽에서 왼쪽으로 순회
각 단계가 끝날 때마다 경계 변수(k, l, m, n)를 갱신하고, 이미 출력한 요소의 개수(count)가 전체 요소 수(total)에 도달하면 탐색을 종료합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
#define R 3
#define C 3
void printCounterClockwiseSpiral(int m, int n, int matrix[R][C]){
int i, k = 0, l = 0;
int count = 0;
int total = m * n;
while (k < m && l < n){
if (count == total)
break;
for (i = k; i < m; ++i){
cout<<matrix[i][l]<<" ";
count++;
}
l++;
if (count == total)
break;
for (i = l; i < n; ++i){
cout<<matrix[m - 1][i]<<" ";
count++;
}
m--;
if (count == total)
break;
if (k < m){
for (i = m - 1; i >= k; --i){
cout<<matrix[i][n - 1]<<" ";
count++;
}
n--;
}
if (count == total)
break;
if (l < n){
for (i = n - 1; i >= l; --i){
cout<<matrix[k][i]<<" ";
count++;
}
k++;
}
}
}
int main() {
int mat[R][C] = {
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9}
};
cout<<"Counter Clockwise Spiral form of the matrix is :\n";
printCounterClockwiseSpiral(R, C, mat);
return 0;
}실행 결과
위 프로그램을 실행하면 행렬의 시계 반대 방향 나선형 순서가 다음과 같이 출력됩니다.
Counter Clockwise Spiral form of the matrix is : 1 4 7 8 9 6 3 2 5
복잡도 분석
- 시간 복잡도: O(m × n) — 행렬의 모든 요소를 정확히 한 번씩 방문합니다.
- 공간 복잡도: O(1) — 추가 자료구조 없이 경계 변수만 사용합니다.