스파이럴(달팽이) 배열 구현하기 - 대칭 축소(nLength) 방식

앞서 설명한 문제의 교재 답지에 있던 방식이다.

문제 정의

5x5 정수 배열을 아래처럼 시계방향 나선형으로 1부터 25까지 채우는 게 목표다.

1   2   3   4    5
16  17  18  19   6
15  24  25  20   7
14  23  22  21   8
13  12  11  10   9

방식 설명

핵심 아이디어는 한 바퀴를 위쪽/오른쪽 + 아래쪽/왼쪽 두 구간으로 쪼개서, 같은 부호(nDirecton)로 x와 y를 순서대로 움직인다. 한라운드가 끝나면 부호를 뒤집고, 다음 루프는 테두리 한 칸 안쪽(nLength -= 2)에서 반복한다. 

nLength는5x5배열 기준 9에서 시작해 2씩 줄어들며 9,7,5,3,1, 다섯 라운드를 수행한다.

안쪽 for문은 매 바퀴 nLength를 반복하는데, 앞쪽 절반(위 or 아래)은 i < nLength/2 +1

void fillSpiralBySymmetry(int arr[SIZE][SIZE]) {
	int x = -1;
	int y = 0;
	int nCounter = 0;
	int i = 0;
	int j = 0;
	int nLength = 9;
	int nDirection = 1;

	for (nLength; nLength > 0; nLength -= 2) {
		for (i = 0; i < nLength; ++i) {
			if (i < nLength / 2 + 1)
				x += nDirection;
			else
				y += nDirection;
			arr[y][x] = ++nCounter;
		}

		nDirection = -nDirection;
	}
}

그림

과정

nLength = 9 첫 바퀴부터 손으로 추적하면 이렇다. (half = nLength/2 + 1)

 

nLength=9, nDirection=+1, half=5, 시작 x=-1, y=0

i=0~4 (x 이동, i<5)   : x=0,1,2,3,4 → arr[0][0..4] = 1,2,3,4,5
i=5~8 (y 이동, i>=5)  : y=1,2,3,4   → arr[1..4][4] = 6,7,8,9

바퀴 종료 후 nDirection = -1

 

nLength=7, nDirection=-1, half=4, 시작 x=4, y=4

i=0~3 (x 이동)  : x=3,2,1,0     → arr[4][3..0] = 10,11,12,13
i=4~6 (y 이동)  : y=3,2,1       → arr[3..1][0] = 14,15,16

바퀴 종료 후 nDirection = +1

 

nLength=5, nDirection=+1, half=3, 시작 x=0, y=1

i=0~2 (x 이동)  : x=1,2,3       → arr[1][1..3] = 17,18,19
i=3~4 (y 이동)  : y=2,3         → arr[2..3][3] = 20,21

바퀴 종료 후 nDirection = -1

 

nLength=3, nDirection=-1, half=2, 시작 x=3, y=3

i=0~1 (x 이동)  : x=2,1         → arr[3][2..1] = 22,23
i=2 (y 이동)    : y=2           → arr[2][1] = 24

바퀴 종료 후 nDirection = +1

 

nLength=1, nDirection=+1, half=1, 시작 x=1, y=2

i=0 (x 이동)    : x=2           → arr[2][2] = 25

25에서 정확히 끝나고, 결과는 switch 방식과 완전히 동일한 스파이럴이 나온다.

바퀴가 진행되며 nLength가 어떻게 안쪽으로 좁혀지는지는 아래 그림으로 표현했다.

각 사각형 테두리가 한 바퀴(nLength 값 하나)에 해당하고, 바깥쪽부터 안쪽으로 9 → 7 → 5 → 3 → 1 순서로 좁혀 들어간다. 색이 짙어질수록 나중 바퀴, 즉 배열 중심에 가까운 바퀴다.

특징 분석

장점

-코드가 압도적으로 짧다 : switch 방식은 case 4개 + 인덱스 보정이 필요했지만, 이 방식은 이중 for문 하나로 전체 로직이 끝난다.

-바퀴 수만큼만 바깥 루프가 돈다 : switch 방식은 while 하나 안에서 25번(칸 수만큼) 전체 루프를 도는 반면, 이 방식은 바깥 for문이 5번(바퀴 수만큼)만 돈다.

-

단점

-홀수 정사각형 전용이다 : nLength = 2*SIZE - 1로 시작해서 2씩 줄어드는 구조 자체가 홀수 크기를 전제로 짜여 있다. SIZE가 짝수면 nLength가 0에서 딱 안 떨어지거나 마지막 바퀴 처리가 어긋나서, 이 로직 자체를 다시 설계해야 한다.

-직사각형(N×M)으로 확장이 안 된다 : nLength 하나로 가로/세로를 동시에 표현하는 구조라서, 가로세로 크기가 다른 배열에는 이 방식이 아예 성립하지 않는다.

-가독성이 낮다 : i < nLength/2 + 1이라는 조건만 보고 "아, 절반까지는 x를 움직이고 나머지는 y를 움직이는구나"를 바로 알아채기 어렵다. 처음 보는 사람은 손으로 트레이스를 돌려봐야 이해된다.

-변형이 어렵다 : 예를 들어 반시계방향으로 바꾸거나 사각형이 아닌 패턴으로 확장하려면, 이 압축된 구조 자체를 뜯어고쳐야 한다. switch 방식처럼 case 순서만 바꾸는 식의 손쉬운 변형이 안 된다.

정리

대칭 축소 방식은 "짧고 영리한 코드"의 전형이다. 문제를 홀수 정사각형이라는 좁은 범위로 한정하는 대신, 그 안에서 대칭성을 최대한 활용해 코드량을 확 줄인 것이다.