Note
**Z 순회(Z-order Traversal)**를 활용하여 분할 정복으로 해결하는 문제입니다.
문제
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
문제 링크: https://www.acmicpc.net/problem/1074
입력
첫째 줄에 정수 N, r, c가 주어진다.
출력
r행 c열을 몇 번째로 방문했는지 출력한다.
제한
- 1 ≤ N ≤ 15
- 0 ≤ r, c < 2N
예제
예제 입력 1:
2 3 1
예제 출력 1:
11
예제 입력 2:
3 7 7
예제 출력 2:
63
문제 분석
이 문제는 Z 순회를 구현하는 문제입니다.
핵심 포인트
- Z 순회: 2N × 2N 배열을 Z 모양으로 탐색
- 분할 정복: 배열을 4등분하여 재귀적으로 처리
- 메모리 최적화: 실제 배열을 생성하지 않고 계산만 수행
왜 배열을 생성하면 안 되는가?
N=15일 때:
- 배열 크기: 2¹⁵ × 2¹⁵ = 1,073,741,824개 원소
- 메모리 부족 발생!
따라서 실제 배열을 생성하지 않고, 재귀적으로 사분면만 계산해야 합니다.
해결 방법
분할 정복 알고리즘을 사용합니다:
- 현재 영역을 4등분
- 목표 좌표가 어느 사분면에 속하는지 판별
- 해당 사분면의 시작 값을 계산
- 재귀적으로 해당 사분면에서 탐색
코드 구현
제공된 코드
import sys
n, r, c = map(int, sys.stdin.readline().split())
def z(start: int, y: int, x: int, size: int):
if size == 1:
print(start)
return
# 사분면별 최소값 주입
mid = size / 2
mid_x = int(x + mid)
mid_y = int(y + mid)
# 사분면 찾기
zone = 0
if r < mid_y and c >= mid_x:
zone = 1
start = start + int((size ** 2) * 1/4)
elif r >= mid_y and c < mid_x:
zone = 2
start = start + int((size ** 2) * 2/4)
elif r >= mid_y and c >= mid_x:
zone = 3
start = start + int((size ** 2) * 3/4)
if zone == 0:
z(start, y, x, size // 2)
elif zone == 1:
z(start, y, mid_x, size // 2)
elif zone == 2:
z(start, mid_y, x, size // 2)
else:
z(start, mid_y, mid_x, size // 2)
z(0, 0, 0, 2 ** n)코드 분석
1. 입력 처리
import sys
n, r, c = map(int, sys.stdin.readline().split())- 입력 최적화를 위해
sys.stdin.readline()사용 - N, r, c를 입력받음
2. 기저 조건
if size == 1:
print(start)
return- 크기가 1×1이면 시작 값이 답
- 더 이상 분할할 수 없음
3. 사분면 분할
mid = size / 2
mid_x = int(x + mid)
mid_y = int(y + mid)- 현재 영역을 4등분하기 위한 중간값 계산
mid_x,mid_y: 사분면 경계
4. 사분면 판별 및 시작 값 계산
zone = 0
if r < mid_y and c >= mid_x:
zone = 1
start = start + int((size ** 2) * 1/4)
elif r >= mid_y and c < mid_x:
zone = 2
start = start + int((size ** 2) * 2/4)
elif r >= mid_y and c >= mid_x:
zone = 3
start = start + int((size ** 2) * 3/4)사분면 판별:
- 사분면 0 (좌상단):
r < mid_y && c < mid_x(기본값) - 사분면 1 (우상단):
r < mid_y && c >= mid_x - 사분면 2 (좌하단):
r >= mid_y && c < mid_x - 사분면 3 (우하단):
r >= mid_y && c >= mid_x
시작 값 계산:
- 각 사분면의 시작 값 = 이전 사분면들의 크기 합
- 사분면 크기:
(size²) / 4 = (size // 2)²
5. 재귀 호출
if zone == 0:
z(start, y, x, size // 2)
elif zone == 1:
z(start, y, mid_x, size // 2)
elif zone == 2:
z(start, mid_y, x, size // 2)
else:
z(start, mid_y, mid_x, size // 2)- 해당 사분면으로 좌표 이동
- 새로운 시작 값과 크기로 재귀 호출
시간 및 공간 복잡도
시간 복잡도
- 재귀 깊이: O(N) - 2N × 2N 배열
- 각 단계: O(1) - 사분면만 확인
- 전체: O(N)
공간 복잡도
- 재귀 스택: O(N)
- 전체: O(N)
심화 이론
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인 경우:
- 배열을 4등분 (각각 2N-1 × 2N-1 크기)
- 각 사분면을 Z 순서로 재귀적으로 탐색
- 사분면 순서: 좌상단 → 우상단 → 좌하단 → 우하단
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:
- 전체 4×4 배열 → half=2
r=3 >= 2, c=1 < 2→ 사분면 2 (좌하단)- 시작 값:
0 + (2²) × 2 = 8 - 새로운 좌표:
(r=3-2=1, c=1-0=1)→(1, 1) - 2×2 배열에서
(1, 1)→ 인덱스 3 - 최종:
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)
관련 알고리즘
- 분할 정복 (Divide and Conquer)
- 재귀 (Recursion)