Yunsu's Log

BOJ 1074: Z

9 min read

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 순회를 구현하는 문제입니다.

핵심 포인트

  1. Z 순회: 2N × 2N 배열을 Z 모양으로 탐색
  2. 분할 정복: 배열을 4등분하여 재귀적으로 처리
  3. 메모리 최적화: 실제 배열을 생성하지 않고 계산만 수행

왜 배열을 생성하면 안 되는가?

N=15일 때:

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

따라서 실제 배열을 생성하지 않고, 재귀적으로 사분면만 계산해야 합니다.

해결 방법

분할 정복 알고리즘을 사용합니다:

  1. 현재 영역을 4등분
  2. 목표 좌표가 어느 사분면에 속하는지 판별
  3. 해당 사분면의 시작 값을 계산
  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)
  • 해당 사분면으로 좌표 이동
  • 새로운 시작 값과 크기로 재귀 호출

개선된 코드

더 명확하고 효율적으로 작성한다면:

import sys
 
readline = sys.stdin.readline
 
def z_order(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 < y + half and c < x + half:
        # 사분면 0 (좌상단)
        return z_order(n, r, c, start, y, x, half)
    elif r < y + half and c >= x + half:
        # 사분면 1 (우상단)
        new_start = start + (half ** 2) * 1
        return z_order(n, r, c, new_start, y, x + half, half)
    elif r >= y + half and c < x + half:
        # 사분면 2 (좌하단)
        new_start = start + (half ** 2) * 2
        return z_order(n, r, c, new_start, y + half, x, half)
    else:
        # 사분면 3 (우하단)
        new_start = start + (half ** 2) * 3
        return z_order(n, r, c, new_start, y + half, x + half, half)
 
n, r, c = map(int, readline().split())
print(z_order(n, r, c))

개선 사항:

  • 함수가 값을 반환하도록 변경 (출력 대신)
  • 변수명을 더 명확하게 (mid → half)
  • 좌표 계산을 더 명확하게 (y + half, x + half)
  • 사분면 판별 로직을 더 명확하게

시간 및 공간 복잡도

시간 복잡도

  • 재귀 깊이: O(N) - 2N × 2N 배열
  • 각 단계: O(1) - 사분면만 확인
  • 전체: O(N)

공간 복잡도

  • 재귀 스택: O(N)
  • 전체: O(N)

예제 동작 과정

예제 입력 1: n=2, r=3, c=1

4×4 배열 (크기 4):

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

재귀 과정:

  1. z(0, 0, 0, 4): 전체 배열, r=3, c=1

    • mid = 4/2 = 2
    • mid_x = 0 + 2 = 2, mid_y = 0 + 2 = 2
    • r=3 >= mid_y=2 && c=1 < mid_x=2 → 사분면 2 (좌하단)
    • start = 0 + int((4²) × 2/4) = 0 + int(16 × 0.5) = 8
    • z(8, 2, 0, 2) 호출

  2. z(8, 2, 0, 2): 좌하단 2×2 영역, r=3, c=1

    • mid = 2/2 = 1
    • mid_x = 0 + 1 = 1, mid_y = 2 + 1 = 3
    • r=3 >= mid_y=3 && c=1 >= mid_x=1 → 사분면 3 (우하단)
    • start = 8 + int((2²) × 3/4) = 8 + int(4 × 0.75) = 8 + 3 = 11
    • z(11, 3, 1, 1) 호출

  3. z(11, 3, 1, 1): 크기 1×1

    • size == 1 → 출력 11 ✓

주의사항

1. 좌표 변환

재귀 호출 시 좌표를 상대 좌표로 변환해야 합니다:

# 절대 좌표를 상대 좌표로 변환
new_r = r - new_y
new_c = c - new_x

2. 사분면 시작 값

각 사분면의 시작 값은:

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

3. 메모리 최적화

실제 배열을 생성하지 않고 계산만 수행해야 합니다. N이 15일 때 배열을 생성하면 메모리 부족이 발생합니다.

관련 알고리즘

그래프 뷰

백링크