[TIL/크래프톤 정글9기] 10일차(백준 Z)

백준 Z

오늘은 이번 주 백준 알고리즘 중 재귀함수가 제일 어려웠다..
아직 N-Queen은 도전도 못했지만 일단 Z를 먼저 풀어보려 한다.

처음에는 혼자 생각한 다음 풀어보려했다. 아직은 알고리즘을 머릿속에 넣고 내가 풀어내는 능력이 부족하여 공책에 그려가며 재귀함수를 어떻게 해야할지 고민을 해보았다.

내 생각에는 2차원 배열로 두고 이걸 4등 분씩 나눠보면 어떨까라는 생각을 했지만 0.5초라는 제한 시간에는 되지 않을거 같았다.

일단 4등분씩 나누고 그 나눈 4등분의 2차원 배열을 쭉 나눠 n이 0이 되면 0을 리턴해 재귀를 끝내는 것 까진 생각했다. 그리고 배열을 나눈 중간점 '$2^n-1$'을 기준으로 우상, 좌상, 우하, 좌하로 내리는 것 까진 생각했지만 이 4개의 사분면에 대해 함수 전달값을 어떻게 바꾸는지 도저히 몰라 같은 기수에 먼저 푸신분이 설명을 해주셔서 잘 알게되었다.

import sys

def Z(n, r, c):
    if n == 0:
        return 0

    half = 2**(n-1)
    
    if r < half and c < half:
        return Z(n-1, r, c)
    elif r < half and c >= half:
        return half*half + Z(n-1, r, c-half)
    elif r >= half and c < half:
        return 2*half*half + Z(n-1, r-half, c)
    else:
        return 3*half*half + Z(n-1, r-half, c-half)
    

input = sys.stdin.readline

N, r, c = map(int, input().split())

print(Z(N, r, c))

[상록님 블로그](> https://velog.io/@strawberry-tree/%EB%B0%B1%EC%A4%80-1074.-Z )

• 변의 길이('$2^n$'-> side), 변의 길이의 절반(side // 2 -> half), 한 사분면의 원소 수 (half ** 2)
• 크기가 '$2^n \times 2^n$'인 배열에서, r행 c열의 방문 순서를 반환하는 함수 Z 정의
• 이때 배열은 half × half 크기인 4개의 사분면으로 나뉘어짐
• x행 y열이 어느 사분면에 속하는지 확인하고, 사분면 내 좌표로 재귀 호출
• 특히 r >= half 혹은 c >= half 인 경우, 사분면 내 좌표를 구할 때 half만큼 빼 주어야 함
• 탐색은 좌상 -> 우상 -> 좌하 -> 우하 사분면 순으로 이루어짐
• 이미 다른 사분면을 거친 경우, 이떼 방문한 원소의 수를 재귀함수의 결과에 더해서 반환
• 사분면마다 area개의 원소 수가 있으므로, 그만큼 더하면 됨