나선형(Spiral) 출력 알고리즘은 행렬의 요소들을 나선 모양으로 순서대로 출력하는 방법입니다. 먼저 첫 번째 행 전체를 왼쪽에서 오른쪽으로 출력한 뒤, 마지막 열을 위에서 아래로, 이어서 마지막 행을 오른쪽에서 왼쪽으로, 그리고 첫 번째 열을 아래에서 위로 출력하는 방식으로 안쪽으로 나선을 그리며 진행합니다.
이 알고리즘의 시간 복잡도는 O(MN)입니다. 여기서 M은 행(row)의 개수, N은 열(column)의 개수를 의미하며, 행렬의 모든 요소를 정확히 한 번씩 방문하기 때문에 최적의 성능을 보입니다.
입력과 출력
입력: 행렬: 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
알고리즘
dispSpiral(mat, m, n)
입력: 행렬 mat, 행의 개수 m, 열의 개수 n.
출력: 행렬의 모든 요소를 나선형 순서로 출력합니다.
동작 원리
알고리즘은 네 개의 경계 변수를 활용하여 동작합니다. currRow(현재 시작 행)와 currCol(현재 시작 열)은 안쪽 경계를, m과 n은 바깥쪽 경계를 나타냅니다. 각 반복마다 다음 순서로 요소를 출력하고 경계를 좁혀 나갑니다.
- 첫 번째 행 출력: currCol부터 n-1까지 왼쪽에서 오른쪽으로 출력한 후 currRow를 1 증가시킵니다.
- 마지막 열 출력: currRow부터 m-1까지 위에서 아래로 출력한 후 n을 1 감소시킵니다.
- 마지막 행 출력: currRow < m인 경우, n-1부터 currCol까지 오른쪽에서 왼쪽으로 출력한 후 m을 1 감소시킵니다.
- 첫 번째 열 출력: currCol < n인 경우, m-1부터 currRow까지 아래에서 위로 출력한 후 currCol을 1 증가시킵니다.
이 과정은 currRow와 currCol이 행렬 범위를 벗어날 때까지 반복됩니다.
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 12 18 17 16 15 14 13 7 8 9 10 11
정리
나선형 출력 알고리즘은 네 방향(오른쪽 → 아래 → 왼쪽 → 위)으로 이동하면서 각 단계마다 경계를 하나씩 줄여가는 방식으로 구현됩니다. 핵심 포인트는 다음과 같습니다.
- 단일 행 또는 단일 열만 남았을 때 중복 출력을 방지하기 위해
currRow < m,currCol < n조건 검사가 필수적입니다. - 시간 복잡도는 O(MN), 공간 복잡도는 추가 배열 없이 O(1)로 효율적입니다.
- 이 기법은 이미지 회전, 2D 배열 탐색 등 다양한 문제에 응용할 수 있습니다.