양의 정수 n이 주어졌을 때, O(1)의 추가 공간만 사용하여 시계 방향으로 회전하는 n×n 나선 행렬(spiral matrix)을 생성하고 출력하는 것이 이 글의 목표입니다.
나선 행렬이란?
나선 행렬은 원의 중심에서 출발해 시계 방향으로 회전하며 값을 채워 나가는 행렬입니다. 이 문제에서는 2 → 4 → 6 → 8 → 10 → 12 → 14 → 16 → 18처럼 연속된 짝수가 나선 형태로 배치된 행렬을 상수 공간 복잡도로 출력해야 합니다.
예시
입력: 3
출력:
9 8 7
2 1 6
3 4 1메모리 제약 없이 코드를 작성하는 것은 쉽지만, 진정으로 좋은 프로그램은 메모리와 시간 두 측면에서 모두 효율적이어야 합니다. 일반적으로 나선 순서를 유지하려면 행렬의 위(top)·오른쪽(right)·아래(bottom)·왼쪽(left) 네 경계마다 루프를 사용해야 하지만, 행렬을 오른쪽 위 절반과 왼쪽 아래 절반, 두 영역으로 나누면 다음 수식을 통해 각 칸의 값을 곧바로 계산할 수 있습니다.
오른쪽 위 절반(i ≤ j)의 경우
mat[i][j] = (n-2*x)*(n-2*x) - (i-x) - (j-x)
왼쪽 아래 절반(i > j)의 경우
mat[i][j] = (n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)
여기서 x는 좌표 (i, j)가 속한 동심원 레이어(층) 번호를 의미하며, i와 j 중 작은 값(a)과 n-1-i, n-1-j 중 작은 값(b)을 비교해 더 작은 쪽으로 결정됩니다.
참고: 이 글에서 작성하는 프로그램은 2의 배수(짝수)로 이루어진 행렬을 출력합니다.
알고리즘
int spiralmatrix(int n)
START
STEP 1: 변수 i, j, a, b, x 선언
STEP 2: FOR i = 0 AND i < n AND i++
FOR j = 0 AND j < n AND j++
(i, j) 중 최솟값을 구해 a에 대입
(n-1-i, n-1-j) 중 최솟값을 구해 b에 대입
a와 b 중 더 작은 값을 x에 대입
IF i <= j THEN
2 * ((n-2*x)*(n-2*x) - (i-x) - (j-x)) 값 출력
ELSE
2 * ((n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)) 값 출력
END LOOP
줄바꿈 출력
END LOOP
STOPC 언어 구현 예제
#include <stdio.h>
// n x n 나선 행렬 출력 함수
int spiralmatrix(int n){
int i, j, a, b, x; // x는 (i, j)번째 원소가 속한 레이어를 저장
for (i = 0; i < n; i++){
for (j = 0; j < n; j++){
// 네 값 중 최솟값 계산
a = ((i<j ? i : j));
b = ((n-1-i) < (n-1-j) ? (n-1-i) : (n-1-j));
x = a < b ? a : b;
// 오른쪽 위 절반
if (i <= j)
printf("%d\t ", 2 * ((n-2*x)*(n-2*x) - (i-x) - (j-x)));
// 왼쪽 아래 절반
else
printf("%d\t ", 2*((n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)));
}
printf("\n");
}
}
int main(int argc, char const *argv[]){
int n = 3;
spiralmatrix(n);
return 0;
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
18 16 14 4 2 12 6 8 10
이처럼 별도의 2차원 배열을 선언하지 않고도 각 좌표가 속한 레이어(x)를 계산해 수식만으로 값을 도출할 수 있으므로, 추가 공간을 O(1)로 유지하면서 n×n 나선 행렬을 효율적으로 출력할 수 있습니다.