항해99 리부트코스 알고리즘 1주 - 3일차 1074 Z

https://www.acmicpc.net/problem/1074

 

문제

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

예제 입력 1 복사

2 3 1

예제 출력 1 복사

11

예제 입력 2 복사

3 7 7

예제 출력 2 복사

63

예제 입력 3 복사

1 0 0

예제 출력 3 복사

0

예제 입력 4 복사

4 7 7

예제 출력 4 복사

63

예제 입력 5 복사

10 511 511

예제 출력 5 복사

262143

예제 입력 6 복사

10 512 512

예제 출력 6 복사

786432

 

 

풀이

 

재귀함수를 이용한다.

def z_order(n, r, c):
    # 기본 크기가 1x1인 경우
    if n == 0:
        return 0
    
    # 절반 크기 계산
    half = 2 ** (n - 1)
    
    # 첫 번째 사분면
    if r < half and c < half:
        return z_order(n - 1, r, c)
    
    # 두 번째 사분면
    elif r < half and c >= half:
        return half * half + z_order(n - 1, r, c - half)
    
    # 세 번째 사분면
    elif r >= half and c < half:
        return 2 * half * half + z_order(n - 1, r - half, c)
    
    # 네 번째 사분면
    else:
        return 3 * half * half + z_order(n - 1, r - half, c - half)

# 입력 받기
n, r, c = map(int, input().split())
# 결과 출력
print(z_order(n, r, c))

 

 

 

1. 왜 문제를 풀려면 4분면으로 쪼개야 하는지?

 

문제를 4분면으로 쪼개는 이유는 Z 순서(Z-order curve)가 재귀적으로 각 사분면을 방문하기 때문이다.

Z 순서란 2차원 배열을 Z 모양으로 순회하며, 작은 부분에서 큰 부분으로 확장하는 방식이다.

배열을 4분면으로 나누면 각 사분면 내에서 동일한 방식으로 순회를 반복할 수 있어 문제를 재귀적으로 해결하기에 적합하다

 

 

2.수학적인 이유:

Z 순서에서는 배열을 4등분한 후 각 사분면을 차례대로 방문한다. 이를 통해 각 사분면의 시작 위치를 알 수 있다.

• 첫 번째 사분면(좌측 상단): 기본 위치
• 두 번째 사분면(우측 상단): 첫 번째 사분면의 크기만큼 이동한 위치
• 세 번째 사분면(좌측 하단): 첫 번째 사분면의 두 배 크기만큼 이동한 위치
• 네 번째 사분면(우측 하단): 첫 번째 사분면의 세 배 크기만큼 이동한 위치

이를 일반화하면, 배열의 크기를 절반으로 줄이고, 해당 좌표를 조정해 작은 문제로 축소할 수 있다.

예를 들어, N×NN \times NN×N 배열에서 좌표 (r,c)(r, c)(r,c)를 방문 순서를 찾으려면 다음과 같이 나눈다.

이 과정을 통해 재귀적으로 문제를 해결하면 전체 방문 순서를 효율적으로 계산할 수 있다.