[Python] 1074 Z 문제 풀이 및 정답코드

728x90

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

본 문제와 같이 배열을 분할하는 문제는 흔히 분할 정복(Divide & Conquer) 기법을 활용하여 해결한다. 특히, 배열이 특정한 패턴을 따르며 순차적으로 탐색되거나 순서가 정해져 있을 경우, 재귀적인 방법이 유용하다. 이번 문제는 조금 오래 걸려서, 제대로 정리해보고자 한다.

1. 문제 유형

배열을 재귀적으로 나누면서 특정 위치를 찾는 문제는 대개 Z-모양 탐색, 쿼드트리 분할, 행렬 곱셈 최적화 등의 유형에서 등장한다. 이러한 문제는 일반적으로 다음과 같은 특징을 가진다.

배열의 크기가 2^n × 2^n 형태로 주어진다.
배열을 4개의 부분으로 나누어 처리할 수 있다.
각 부분의 크기가 절반으로 줄어들면서 탐색이 진행된다.

위의 특징을 고려하면, 이 문제는 재귀적으로 배열을 나누어 탐색하는 방식으로 접근하는 것이 적절하다.

2. 핵심 아이디어

배열을 크기별로 나누어 특정 좌표(r, c)가 어느 영역에 속하는지를 찾는다. 이를 위해 배열을 4개의 사분면으로 구분하고, 해당 좌표가 어느 사분면에 위치하는지를 판별하여 탐색을 진행한다.

배열이 크기에 따라 나누어지는 방식은 다음과 같다.

배열이 2×2일 때 (n=1)→ 직접 탐색 가능함

배열이 4×4일 때 (n=2)→ 4개의 부분으로 나누어 탐색 진행

배열이 8×8일 때 (n=3)→ 절반씩 나누어가며 탐색 진행

3. 해결 방법

(1) 배열을 절반씩 나누면서 위치 탐색

배열 크기의 절반(half = 2^(n-1))을 기준으로 (r, c)의 위치를 판별한다. 위치에 따라 사분면을 결정하고, 해당 사분면의 시작 위치를 더하면서 재귀적으로 탐색한다.

1사분면 (좌상단): 0 ≤ r < half, 0 ≤ c < half
2사분면 (우상단): 0 ≤ r < half, half ≤ c < size
3사분면 (좌하단): half ≤ r < size, 0 ≤ c < half
4사분면 (우하단): half ≤ r < size, half ≤ c < size

이를 이용하여 위치를 좁혀가며 탐색을 진행한다.

(2) 종료 조건 설정

배열의 크기가 1×1이 되면 더 이상 나눌 필요가 없다. 즉, n == 0이 되면 최종적으로 계산된 값을 반환하면 된다.

4. 코드 구현

위의 개념을 적용하여 코드로 구현하면 다음과 같다.

# 배열 탐색을 위한 재귀 함수
def dfs(n, value, nr, nc):
    if n == 0:
        return value  # 최종 값 반환

    half = 2 ** (n-1)  # 절반 크기

    if nr < half and nc < half:  # 1사분면
        plane = 0
    elif nr < half and nc >= half:  # 2사분면
        plane = 1
        nc -= half
    elif nr >= half and nc < half:  # 3사분면
        plane = 2
        nr -= half
    else:  # 4사분면
        plane = 3
        nr -= half
        nc -= half

    return dfs(n-1, value + (half * half) * plane, nr, nc)

# 입력 처리 및 실행
n, r, c = map(int, input().split())  # 크기, 행, 열
print(dfs(n, 0, r, c))

배열을 재귀적으로 나누어 탐색하는 문제는 분할 정복 기법을 사용하여 해결할 수 있다. 핵심은 (r, c)의 위치를 사분면별로 탐색하며, 배열 크기를 절반씩 줄여가는 과정이다. 위와 같은 분할정복 기법 사용 문제는 생각보다 만났을 때, 당황스러웠다.

DP와 분할정복 문제를 여러개 풀어보면서 익숙해져야겠다.