[백준 / 파이썬] 1074번: Z

1074번: Z

정답 코드

import sys
input = sys.stdin.readline


def Z(n: int, r: int, c: int):
    """_summary_

    Args:
        n (int): 2^n
        r (int): row
        c (int): col

    Returns:
        _type_: r행 c열을 몇 번째로 방문
    """
    
    # 종료 조건
    if n == 0:
        return 0
    
    half = 2 ** (n-1)
    subarray = (r >= half) * 2 + (c >= half)
    """_summary_
    subarray가 0일 경우: 현재 위치 (r, c)가 크기 2^n인 격자의 좌상단 구역에 속함
    subarray가 1일 경우: 현재 위치 (r, c)가 크기 2^n인 격자의 우상단 구역에 속함
    subarray가 2일 경우: 현재 위치 (r, c)가 크기 2^n인 격자의 좌하단 구역에 속함
    subarray가 3일 경우: 현재 위치 (r, c)가 크기 2^n인 격자의 우하단 구역에 속함
    """
    subarray_r = r % half
    subarray_c = c % half
    return ((subarray * half * half)
            + Z(n-1, subarray_r, subarray_c))


n, r, c = map(int, input().split())
print(Z(n, r, c))

문제 풀이

1. `Z` 함수는 `n`, `r`, `c` 세 개의 인자를 받습니다. `n`은 2^n의 크기로 된 격자에 해당하는 지수이고, `r`과 `c`는 원하는 좌표의 행과 열을 나타냅니다.
2. 함수 내부에는 재귀적으로 동작하는 부분이 있습니다. 재귀 함수는 크기가 2^n인 격자를 4분할하여 Z 모양으로 탐색하면서 원하는 좌표의 값을 찾게 됩니다.
3. `Z` 함수의 종료 조건은 `n`이 0일 때입니다. 이때는 크기가 1인 격자이므로 탐색할 필요 없이 0을 반환합니다.
   `half` 변수는 현재 격자의 크기를 반으로 줄인 크기(2^(n-1))를 나타냅니다.
4. `subarray` 변수는 현재 위치 `(r, c)`가 속하는 구역을 나타냅니다. 구역은 0부터 3까지의 값을 가지며, 크기가 2^n인 격자를 좌상단, 우상단, 좌하단, 우하단으로 나눌 때의 위치에 따라 결정됩니다.
5. `subarray_r`과 `subarray_c` 변수는 현재 격자 내에서의 좌표를 나타냅니다. 크기가 2^n인 격자를 4분할하여 재귀적으로 탐색할 때, 현재 격자 내에서의 상대적인 위치를 계산하기 위해 사용됩니다.
6. 재귀 함수의 반환 값은 `subarray`에 따라 올바른 구역을 선택한 뒤, 해당 구역 내에서 재귀적으로 다시 `Z` 함수를 호출하여 결과를 얻습니다. 이때, 반환 값을 구하는 과정에서 원하는 좌표의 값을 찾게 됩니다.
7. 마지막으로, 함수에 주어진 `n`, `r`, `c`를 입력으로 받아서 `Z` 함수를 호출하고, 그 결과를 출력합니다.