스파이럴(달팽이) 배열 구현하기 - 경계값(Boundary) 방식

이번엔 스파이럴 배열 문제의 "정석" 풀이로 통하는 경계값 방식을 정리한다. 코딩테스트에서 스파이럴/나선 행렬 문제가 나오면 가장 먼저 떠올려야 하는 접근이다.

 

방식 설명

핵심 아이디어는 앞선 두 방식과 또 다르다. 배열 값이 채워졌는지(0인지) 보는 대신, 네 방향의 한계선(top, bottom, left, right)을 숫자로 직접 관리한다. 한 방향을 채우면 그 방향의 경계선을 안쪽으로 한칸 좁힌다.

switch 방식이 "배열 값이 0인지"로 다음 칸을 판단했다면, 이 방식은 배열 값을 전혀 들여다보지 않고 오직 숫자 네 개(top, bottom, left, right)만으로 어디까지 채웠는지 판단한다. 그래서 한 바퀴가 끝날 때마다 ++top, --right, --bottom, ++left로 테두리가 정확히 한 칸씩 안쪽으로 좁혀진다.

if (top <= bottom)과 if (left <= right) 체크가 있는 이유는, 홀수 크기 배열에서 정가운데 행/열을 두 번 채우는 실수를 막기 위해서다. 예를 들어 5x5의 마지막 바퀴는 정중앙 칸 하나뿐인데, 이 체크가 없으면 그 칸을 아래쪽 행 채우기와 왼쪽 열 채우기에서 중복으로 건드리게 된다.

void fillSpiralByBoundary(int arr[SIZE][SIZE]) {
	int value = 0;

	int top = 0;
	int bottom = SIZE - 1;
	int left = 0;
	int right = SIZE - 1;

	while (top <= bottom && left <= right) {
		for (int x = left; x <= right; x++) {
			arr[top][x] = ++value;
		}
		++top;

		for (int y = top; y <= bottom; y++) {
			arr[y][right] = ++value;
		}
		--right;

		if (top <= bottom) {
			for (int x = right; x >= left; x--) {
				arr[bottom][x] = ++value;
			}
			--bottom;
		}

		if (left <= right) {
			for (int y = bottom; y >= top; y--) {
				arr[y][left] = ++value;
			}
			++left;
		}
	}

}

그림

과정

5x5 기준으로 top, bottom, left, right가 어떻게 좁혀지는지 단계별로 추적하면 이렇다.

 

[1바퀴] top=0, bottom=4, left=0, right=4

위쪽 행 (x: 0→4)   : arr[0][0..4] = 1,2,3,4,5        → ++top (top=1)
오른쪽 열 (y: 1→4) : arr[1..4][4] = 6,7,8,9           → --right (right=3)
아래쪽 행 (x: 3→0) : arr[4][3..0] = 10,11,12,13       → --bottom (bottom=3)
왼쪽 열 (y: 3→1)   : arr[3..1][0] = 14,15,16          → ++left (left=1)

[2바퀴] top=1, bottom=3, left=1, right=3

위쪽 행 (x: 1→3)   : arr[1][1..3] = 17,18,19          → ++top (top=2)
오른쪽 열 (y: 2→3) : arr[2..3][3] = 20,21              → --right (right=2)
아래쪽 행 (x: 2→1) : arr[3][2..1] = 22,23              → --bottom (bottom=2)
왼쪽 열 (y: 2→2)   : arr[2][1] = 24                    → ++left (left=2)

[3바퀴] top=2, bottom=2, left=2, right=2

위쪽 행 (x: 2→2)   : arr[2][2] = 25                    → ++top (top=3)
오른쪽 열           : top(3) > bottom(2)라 for문 자체가 안 돎
--right (right=1)
if (top<=bottom) → 3<=2 거짓 → 아래쪽 행 스킵
if (left<=right) → 2<=1 거짓 → 왼쪽 열 스킵

while (top<=bottom) → 3<=2 거짓 → 종료

결과는 switch 방식, 답지 방식과 완전히 동일한 스파이럴이다. 다만 이번엔 한 바퀴(ring) 단위로 안쪽까지 몇 겹인지를 기준으로 색을 나눠 봤다.

바깥쪽 테두리(1바퀴, 값 1~16)가 가장 넓고, 그 안쪽 테두리(2바퀴, 값 17~24)가 한 겹 좁고, 정중앙(3바퀴, 값 25)이 마지막이다. 5x5는 딱 3겹으로 끝난다.

특징 분석

장점

 

• 배열 값에 전혀 의존하지 않는다 : switch 방식이나 방향배열 방식은 "0인지 아닌지"로 다음 칸을 판단하지만, 이 방식은 오직 경계값 숫자만으로 판단한다. 그래서 배열에 어떤 값이 들어가든(심지어 0이 포함된 값이든) 로직이 안전하다.
• for문 인덱스 보정이 필요 없다 : switch 방식은 for문이 끝난 뒤 --x, ++y로 되돌리는 보정이 필요했지만, 이 방식은 for (x = left; x <= right; x++)처럼 범위(<=)가 정확히 맞아떨어져서 별도 보정이 없다.
• 홀수/짝수 크기 모두 자연스럽게 지원한다 : if (top <= bottom), if (left <= right) 체크가 중앙 칸 중복 채움을 막아주기 때문에, SIZE가 짝수든 홀수든 코드 수정 없이 그대로 동작한다.
• 직사각형(N×M)으로 쉽게 확장된다 : top/bottom과 left/right이 애초에 가로세로를 독립적으로 관리하므로, 초기값만 가로/세로 크기에 맞게 따로 잡으면 정사각형이 아니어도 그대로 동작한다.
• 코딩테스트의 표준 풀이다 : 스파이럴/나선 행렬 문제가 나왔을 때 면접관이나 채점 기준이 기대하는 방식이 보통 이거다.

단점

• 경계 변수 4개(top, bottom, left, right)를 동시에 관리해야 해서, 처음 볼 때는 switch 방식보다 변수 흐름 파악에 시간이 좀 더 걸릴 수 있다.
• if (top <= bottom), if (left <= right) 체크의 의미(중앙 칸 중복 방지)를 모르면, 이 두 줄이 왜 있는지 이해하기 어렵다.

정리

경계값 방식은 switch 방식의 장점(배열 크기·모양에 안 흔들리는 확장성)과 대칭 축소 방식의 장점(인덱스 보정 없이 깔끔함)을 동시에 가져간 형태에 가깝다. 그래서 코딩테스트나 실무에서 "스파이럴 행렬을 채워라" 같은 문제가 나오면, 이 경계값 방식을 표준 풀이로 익혀두는 게 가장 범용적이다.