네 경계를 줄이며 읽는 Spiral Matrix: 중복 없는 순회의 불변조건

이 글의 시각적 출발점은 Instagram의 Spiral Matrix 포스트입니다. 원본 캡션을 옮기거나 이미지·영상·코드 자산을 사용하지 않았습니다. 아래 실행 보드, 코드, 증명과 테스트는 네 경계 불변조건을 직접 확인할 수 있도록 독립적으로 다시 구성했습니다.

먼저 결론

Spiral Matrix는 방향을 오른쪽·아래·왼쪽·위로 바꾸는 문제처럼 보이지만, 방향만 저장하면 모서리에서 언제 멈춰야 하는지가 계속 예외가 된다. 더 안정적인 상태는 아직 방문하지 않은 영역을 감싸는 네 경계다.

• top: 남은 영역의 가장 위 행
• right: 남은 영역의 가장 오른쪽 열
• bottom: 남은 영역의 가장 아래 행
• left: 남은 영역의 가장 왼쪽 열

각 라운드에서 위 행, 오른쪽 열, 아래 행, 왼쪽 열을 시계 방향으로 읽고 방금 소비한 경계를 안쪽으로 한 칸 옮긴다. 핵심은 다음 불변조건이다.

바깥 반복이 시작될 때, 아직 출력하지 않은 셀은 정확히 top..bottom × left..right가 만드는 닫힌 직사각형 안에 있으며, 그 바깥의 모든 셀은 시계 방향 순서로 정확히 한 번 출력되어 있다.

이 문장을 유지하면 정사각형뿐 아니라 직사각형, 한 행, 한 열, 홀수 크기의 중심 셀도 같은 코드로 처리된다. 시간은 모든 셀을 한 번 방문하므로 O(mn)이고, 반환하는 출력 배열을 제외한 추가 작업 공간은 O(1)이다.

보드는 현재 셀과 이동 방향, 네 경계, 아직 남은 직사각형, 지금까지의 출력 순서와 실행 중인 코드 줄을 같은 frame에 보여준다. 애니메이션의 색은 설명 수단일 뿐 정답의 근거는 경계 불변조건과 중복 방지 guard다.

입력 계약부터 고정한다

이 글의 함수는 유한한 직사각형 2차원 배열을 입력으로 받는다. 행의 수를 m, 열의 수를 n이라고 하자.

1. 모든 행의 길이는 같아야 한다. 길이가 다른 ragged array는 이 계약 밖이며 명시적으로 거부한다.
2. 빈 배열 []과 열이 없는 [[]]은 빈 출력을 반환한다.
3. 셀 값은 숫자로 표시하지만 알고리즘은 값을 비교하지 않는다. 문자열이나 객체도 같은 위치 순회가 가능하다.
4. 입력 행과 셀을 교환하거나 표시용 marker를 기록하지 않는다. 반환값은 새 배열이다.
5. 이 글에서 “추가 공간 O(1)”은 결과 배열을 제외한 작업 상태만 센다. m×n개의 결과를 실제 배열로 돌려주면 반환 공간은 당연히 O(mn)이다.

JavaScript API라면 number[][]라는 타입만으로 직사각형을 보장할 수 없다. public boundary에서 첫 행의 길이를 기준으로 모든 행을 검증하거나, 생성 단계에서 shape가 보장되는 전용 Matrix 타입을 받는 편이 안전하다. 검증 비용도 전체 원소 수보다 크지 않으므로 O(m)에 가깝고 전체 O(mn) 상한을 바꾸지 않는다.

상태는 좌표가 아니라 남은 직사각형이다

초기 경계는 다음과 같다.

• top = 0
• bottom = m - 1
• left = 0
• right = n - 1

top <= bottom && left <= right일 때만 남은 셀이 있다. 한 라운드는 네 구간으로 나뉜다.

1. (top, left)에서 (top, right)까지 오른쪽으로 읽고 top++ 한다.
2. 새 top에서 bottom까지 right 열을 아래로 읽고 right-- 한다.
3. top <= bottom && left <= right이면 bottom 행을 오른쪽에서 왼쪽으로 읽고, 같은 조건 블록 안에서 bottom-- 한다.
4. 갱신된 경계로 top <= bottom && left <= right를 다시 검사한다. 참이면 left 열을 아래에서 위로 읽고, 같은 조건 블록 안에서 left++ 한다.

첫 두 구간 뒤에 guard를 다시 검사하는 이유가 중요하다. 바깥 고리를 읽는 도중 남은 직사각형의 높이나 너비 중 하나라도 0이 될 수 있기 때문이다. 세 번째와 네 번째 구간은 모두 높이와 너비가 양수인지 함께 검사한다. guard가 거짓이면 해당 순회뿐 아니라 그 구간의 bottom-- 또는 left++도 실행하지 않는다. 처음 while 조건이 참이었다는 사실은 뒤쪽 구간까지 계속 참임을 보장하지 않는다.

3×4를 한 라운드씩 추적한다

다음 행렬을 생각하자.

첫 고리는 1, 2, 3, 4 → 8, 12 → 11, 10, 9 → 5다. 네 경계를 줄인 뒤 남은 직사각형은 r1의 c1..c2, 즉 6, 7뿐이다. 두 번째 라운드가 그 둘을 읽으면 출력은 다음과 같다.

[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

각 구간이 모서리를 공유하지만 중복되지 않는 이유도 경계 갱신 순서에 있다. 위 행을 읽은 직후 top을 내리므로 오른쪽 열은 오른쪽 위 모서리를 다시 읽지 않는다. 오른쪽 열 뒤 right를 줄이므로 아래 행도 오른쪽 아래 모서리를 다시 읽지 않는다. 같은 방식으로 아래와 왼쪽 모서리도 한 번만 소유된다.

정확성 증명

초기화

아무 셀도 출력하지 않았을 때 아직 방문하지 않은 셀은 전체 행렬 0..m-1 × 0..n-1이다. 네 경계는 정확히 그 직사각형을 가리키고 바깥에는 셀이 없으므로 불변조건이 성립한다. 빈 행렬이나 0열 행렬은 시작부터 while 조건이 거짓이고 빈 출력이 정확하다.

유지

반복 시작 시 불변조건이 참이라고 가정한다.

• 위 구간은 남은 직사각형의 top 행을 왼쪽부터 오른쪽까지 정확히 한 번 읽는다. top++ 뒤 그 행은 남은 영역에서 제외된다.
• 오른쪽 구간은 갱신된 top부터 bottom까지 읽으므로 방금 읽은 오른쪽 위 모서리를 포함하지 않는다. right-- 뒤 그 열도 제외된다.
• 아래쪽 guard는 top <= bottom && left <= right일 때만 참이다. 즉 높이와 너비가 모두 남은 경우에만 아래 행을 읽고 bottom-- 한다. 오른쪽 경계도 이미 줄었으므로 오른쪽 아래 모서리를 다시 읽지 않는다. 어느 한 경계 쌍이라도 교차했다면 순회와 축소를 모두 건너뛴다.
• 왼쪽 guard도 갱신된 경계에서 같은 전체 조건을 검사한다. 높이와 너비가 모두 남은 경우에만 왼쪽 열을 읽고 left++ 한다. 위와 아래 경계가 이미 줄었으므로 두 왼쪽 모서리를 다시 읽지 않으며, 빈 직사각형의 열을 소비했다고 기록하지도 않는다.

따라서 이번 고리의 각 셀은 정확히 한 번 추가되고, 경계를 줄인 뒤 남은 미방문 셀은 다시 하나의 더 작은 닫힌 직사각형이다. 출력은 이전 고리 뒤에 현재 고리의 시계 방향 순서가 이어지므로 불변조건이 보존된다.

종료

각 라운드는 적어도 한 행이나 한 열을 소비해 경계 사이의 크기를 줄인다. 결국 top > bottom 또는 left > right가 되어 반복이 끝난다. 불변조건에 따르면 종료 시 경계 안에는 미방문 셀이 없고, 경계 밖의 모든 셀은 이미 정확히 한 번 출력됐다. 그러므로 결과는 전체 행렬의 올바른 나선 순서다.

중복 방지 guard가 막는 네 가지 경계 사례

한 행: 1×N

첫 번째 오른쪽 이동이 모든 셀을 소비하고 top이 bottom을 넘어선다. 두 full guard가 모두 거짓이므로 아래쪽·왼쪽 순회와 bottom--·left++를 실행하지 않는다. 높이 검사가 빠진 아래쪽 구간은 같은 행을 역순으로 다시 넣을 수 있다. 올바른 결과는 왼쪽에서 오른쪽으로 한 번뿐이다.

한 열: N×1

위 구간이 첫 셀을 읽고 오른쪽 구간이 나머지 셀을 아래로 읽는다. 그 뒤 right가 left보다 작으므로 아래쪽과 왼쪽의 두 full guard가 모두 거짓이다. 따라서 두 순회와 bottom--·left++를 실행하지 않는다. 너비 검사가 빠진 왼쪽 구간은 같은 열을 위로 다시 방문할 수 있다.

홀수 정사각형의 중심

3×3이나 5×5에서는 마지막에 1×1 직사각형이 남는다. 위 구간이 중심을 한 번 읽은 직후 높이가 0이 된다. 두 full guard가 모두 거짓이므로 뒤쪽 순회와 경계 축소 없이 중심은 정확히 한 번만 출력된다.

직사각형과 매우 얇은 띠

2×N이나 N×2에서는 한 라운드 안에서 높이 또는 너비가 먼저 소진된다. 매 방향을 같은 네 번의 loop로 무조건 실행하면 마지막 행·열이 겹친다. 네 경계 방식은 행렬이 정사각형이라는 가정을 하지 않고 각 구간 직전에 실제 남은 차원을 본다.

복잡도를 정확히 세기

각 셀은 한 구간에만 소속되어 한 번 append된다. 네 개의 for loop가 라운드마다 보이더라도 전체 반복 횟수의 합은 mn이다.

• 시간: O(mn)
• 경계 변수와 loop index: O(1)
• 반환 출력 배열: O(mn)
• 입력을 복사하지 않는 경우 입력 추가 복사: 0

“네 방향이므로 O(4mn)”이라고 쓸 필요는 없다. 4는 상수이고 더 중요한 사실은 각 셀이 중복 없이 한 번만 처리된다는 점이다. 반대로 결과 배열까지 숨기면서 전체 공간을 O(1)이라고 말하면 API가 실제로 할당하는 메모리를 누락한다.

출력을 한꺼번에 보관할 필요가 없다면 generator로 좌표나 값을 하나씩 yield할 수 있다. 이 경우 consumer가 즉시 처리한다는 조건에서 traversal 자체의 추가 공간은 O(1)로 유지된다. 다만 generator 객체와 consumer가 보관하는 데이터는 별도 비용이다.

immutable API와 실패 계약

방문 표시를 위해 셀 값을 sentinel로 바꾸는 구현도 가능하지만 다음 문제가 생긴다.

• sentinel이 실제 데이터와 충돌할 수 있다.
• readonly 입력이나 공유된 배열을 손상한다.
• 예외가 중간에 발생하면 부분 변경된 입력이 남는다.
• 값 타입이 객체라면 얕은 복사와 mutation 경계가 더 복잡해진다.

네 경계 구현은 위치 상태만 바꾸므로 입력을 수정할 이유가 없다. 실전 API는 다음처럼 결과와 오류를 구분할 수 있다.

• 유효한 빈 행렬: 빈 결과
• ragged input: RangeError 또는 명시적인 validation error
• 지나치게 큰 행렬: 원소 수·반환 크기 상한 검사
• sparse matrix: dense 직사각형 순회와 다른 API 사용 검토

m×n을 계산할 때 숫자 overflow나 메모리 예산도 확인해야 한다. JavaScript 배열은 이론적인 index 범위보다 실제 heap 한도가 먼저 오며, 거대한 결과 배열을 만들기 전에 rows * columns와 요청 제한을 비교하는 편이 안전하다.

테스트 전략

예시 몇 개의 출력만 비교하면 guard 하나를 빠뜨린 버그를 놓치기 쉽다. 다음 계약을 함께 검사한다.

1. 3×4 결과가 [1,2,3,4,8,12,11,10,9,5,6,7]이다.
2. 1×N은 입력 행과 같고 N×1은 위에서 아래 순서다.
3. 3×3의 중심 셀은 마지막에 정확히 한 번 나타난다.
4. 빈 배열과 0열 행렬은 빈 결과다.
5. ragged array는 조용히 잘못 읽지 않고 거부된다.
6. 입력 배열은 실행 전후 deep equality가 유지된다.
7. 방문 좌표의 수와 Set 크기가 모두 mn이다.
8. 모든 출력 값이 유일하다고 가정하지 않는다. 값이 중복돼도 좌표 기준으로 정확히 한 번 방문해야 한다.

property-based test에서는 작은 m, n을 생성하고 각 셀에 고유 좌표 ID를 넣는다. 결과 길이가 mn인지, 모든 ID가 정확히 한 번 있는지, 연속한 두 좌표가 같은 행이나 열에서 인접한지 확인할 수 있다. 마지막 성질만으로 시계 방향을 모두 증명하지는 못하므로 작은 reference 구현과 결과도 비교한다.

운영 코드로 확장할 때

UI table, image tensor, game board처럼 메모리에 있는 dense matrix라면 이 구현으로 충분하다. 그러나 이름이 비슷해도 다음 문제는 별도 설계가 필요하다.

• 파일이나 원격 tile처럼 random access가 비싼 데이터는 나선 순서가 cache와 I/O locality를 악화시킬 수 있다.
• linked representation이나 sparse matrix는 네 경계 index가 자연스럽지 않다.
• matrix가 실행 중 바뀌면 처음 검증한 shape와 실제 row 길이가 달라질 수 있다. immutable snapshot 또는 동시성 계약이 필요하다.
• 좌표만 필요하면 값을 복사하지 말고 { row, column } iterator를 제공하는 편이 재사용하기 쉽다.
• 매우 큰 board를 화면에 그릴 때는 traversal 계산보다 DOM cell 수가 병목이다. virtualization이나 canvas rendering을 별도로 적용한다.

마지막 원칙

Spiral Matrix를 네 방향 암기 문제로 풀지 말자. 아직 방문하지 않은 셀이 어떤 직사각형을 이루는지, 그리고 한 행이나 한 열이 사라진 뒤 다음 구간을 실행해도 되는지를 상태로 적으면 구현, 증명과 테스트가 같은 말을 하게 된다.