Yunsu's Log

Z 순회 (Z-order Traversal)

6 min read

Note

**Z 순회(Z-order Traversal)**는 2차원 배열을 Z 모양으로 재귀적으로 탐색하는 방법입니다. 분할 정복 알고리즘을 활용합니다.

Z 순회란?

**Z 순회(Z-order Traversal)**는 2N × 2N 크기의 2차원 배열을 Z 모양으로 탐색하는 방법입니다.

Z 모양 탐색 순서

2×2 배열의 경우:

0 1
2 3

탐색 순서: 0 → 1 → 2 → 3 (Z 모양)

재귀적 분할

N > 1인 경우:

  1. 배열을 4등분 (각각 2N-1 × 2N-1 크기)
  2. 각 사분면을 Z 순서로 재귀적으로 탐색
  3. 사분면 순서: 좌상단 → 우상단 → 좌하단 → 우하단

Z 순회의 구조

기본 패턴

┌─────┬─────┐
│  0  │  1  │
├─────┼─────┤
│  2  │  3  │
└─────┴─────┘

각 사분면도 동일한 Z 순서로 탐색됩니다.

재귀적 구조

전체 배열 (2N × 2N)
├─ 사분면 0 (좌상단): 0 ~ (2N-1)² - 1
├─ 사분면 1 (우상단): (2N-1)² ~ 2 × (2N-1)² - 1
├─ 사분면 2 (좌하단): 2 × (2N-1)² ~ 3 × (2N-1)² - 1
└─ 사분면 3 (우하단): 3 × (2N-1)² ~ 4 × (2N-1)² - 1

Z 순회 구현

기본 구현

def z_order_traversal(n, r, c, start=0, y=0, x=0, size=None):
    if size is None:
        size = 2 ** n
    
    # 기저 조건: 크기가 1×1
    if size == 1:
        return start
    
    # 사분면으로 분할
    half = size // 2
    
    # 사분면 찾기
    if r < half and c < half:
        # 사분면 0 (좌상단)
        return z_order_traversal(n, r, c, start, y, x, half)
    elif r < half and c >= half:
        # 사분면 1 (우상단)
        new_start = start + (half ** 2) * 1
        return z_order_traversal(n, r, c, new_start, y, x + half, half)
    elif r >= half and c < half:
        # 사분면 2 (좌하단)
        new_start = start + (half ** 2) * 2
        return z_order_traversal(n, r, c, new_start, y + half, x, half)
    else:
        # 사분면 3 (우하단)
        new_start = start + (half ** 2) * 3
        return z_order_traversal(n, r, c, new_start, y + half, x + half, half)

사분면별 시작 값

각 사분면의 시작 값은:

  • 사분면 0: start
  • 사분면 1: start + (half²) × 1
  • 사분면 2: start + (half²) × 2
  • 사분면 3: start + (half²) × 3

Z 순회의 특징

시간 복잡도

  • O(N): 재귀 깊이가 N (2N × 2N 배열)
  • 각 단계에서 사분면만 확인하므로 O(1)
  • 전체: O(N)

공간 복잡도

  • O(N): 재귀 호출 스택 깊이
  • 실제 배열을 생성하지 않고 계산만 하므로 메모리 효율적

실제 예시

예시: N=2, 4×4 배열

0  1  4  5
2  3  6  7
8  9  12 13
10 11 14 15

탐색 순서: 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 12 → 13 → 14 → 15

사분면 분할:

  • 사분면 0 (좌상단): 0~3
  • 사분면 1 (우상단): 4~7
  • 사분면 2 (좌하단): 8~11
  • 사분면 3 (우하단): 12~15

예시: (r=3, c=1) 찾기

N=2, r=3, c=1:

  1. 전체 4×4 배열 → half=2
  2. r=3 >= 2, c=1 < 2 → 사분면 2 (좌하단)
  3. 시작 값: 0 + (2²) × 2 = 8
  4. 새로운 좌표: (r=3-2=1, c=1-0=1) → (1, 1)
  5. 2×2 배열에서 (1, 1) → 인덱스 3
  6. 최종: 8 + 3 = 11

메모리 최적화

배열 생성 없이 계산

전체 배열을 생성하지 않고, 재귀적으로 사분면만 계산하면:

  • 메모리: O(N) - 재귀 스택만
  • 시간: O(N) - 사분면만 확인

배열 생성 시 문제

N이 크면 (예: N=15):

  • 배열 크기: 2¹⁵ × 2¹⁵ = 1,073,741,824개 원소
  • 메모리 부족 발생!

사분면 판별

조건

주어진 좌표 (r, c)가 어느 사분면에 속하는지:

  • 사분면 0 (좌상단): r < half && c < half
  • 사분면 1 (우상단): r < half && c >= half
  • 사분면 2 (좌하단): r >= half && c < half
  • 사분면 3 (우하단): r >= half && c >= half

좌표 변환

각 사분면으로 이동할 때 좌표를 조정:

  • 사분면 0: (r, c) 그대로
  • 사분면 1: (r, c - half)
  • 사분면 2: (r - half, c)
  • 사분면 3: (r - half, c - half)

관련 알고리즘

그래프 뷰

백링크