[Baekjoon] 1074: Z - (C3, G5) Divide&Conquer, Recursion

문제
한수는 크기가 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

1074번: Z

 

분할 정복 기법과 재귀 호출을 이용하는 꽤나 어려운 문제. 다음과 같이 사분면을 정의한다고 해보자. 

0	1
2	3

 

N = k라 할때, 각 사분면(i)에 대해 첫 번째 번호(0,0)는 전체 사분면의 시작 번호 + $2^{2 \times{(k-1)}} \times i$이다. N = 3, r = 6, c = 3이라 할 때 (6, 3)은 2사분면에 위치한다. k = 3, i = 2이므로 (r, c)가 위치한 사분면의 시작 번호는 $ 0 + 2^{2 \times{(3-1)}} \times 2 = 32$이다.

 

2사분면을 다시 4등분하자. 2사분면 내에서 (r, c)의 상대적 위치는 (6 - 4, 3) = (2, 3)이다. 즉, r >= $2^{k-1}$ 이거나 c >= $2^{k-1}$이면 각각 r - $2^{k-1}$, c - $2^{k-1}$로 조정된다. 

 

2사분면을 4등분했으므로 k = 2이고 시작 번호는 32, 좌표는 (2, 3), 따라서 3사분면이다. 3사분면의 시작 번호는 $32 + 2^{2 \times{(2-1)}} \times 3 = 44$이다. 

 

이와 같이 반복하면 k = 0이 되고, 누적된 시작 번호 값이 (r, c)를 방문하는 순서가 된다. 

 

이를 위해 다음과 같이 사분면 정의 함수와, 좌표 조정 함수를 정의한다. 

 

int calQuadrant(int scale, int r, int c) // 사분면 정의
{
    if (r < scale && c < scale)
        return 0;
    if (r < scale && c >= scale)
        return 1;
    if (r >= scale && c < scale)
        return 2;

    return 3;
}

void setCoord(int scale, int &r, int &c) // 좌표 조정
{
    if (r >= scale)
        r -= scale;
    if (c >= scale)
        c -= scale;
}

 

그리고 다음과 같이 z 함수를 정의하면 문제 해결

int z(int N, int r, int c)
{
    if(!N)
        return 0;
    
    int unit = (int)pow(2, 2 * (N - 1)); // 각 사분면의 시작 번호
    int scale = (int)pow(2, N - 1); // 분할 크기
    int quadrant = calQuadrant(scale, r, c); // 주어진 좌표의 사분면

    int base = unit * quadrant; // 현재 사분면의 시작 번호
    setCoord(scale, r, c); // 좌표 조정

    return base + z(N-1, r, c);
}

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int calQuadrant(int scale, int r, int c) // 사분면 정의
{
    if (r < scale && c < scale)
        return 0;
    if (r < scale && c >= scale)
        return 1;
    if (r >= scale && c < scale)
        return 2;

    return 3;
}

void setCoord(int scale, int &r, int &c) // 좌표 조정
{
    if (r >= scale)
        r -= scale;
    if (c >= scale)
        c -= scale;
}

int z(int N, int r, int c)
{
    if(!N)
        return 0;
    
    int unit = (int)pow(2, 2 * (N - 1)); // 각 사분면의 시작 번호
    int scale = (int)pow(2, N - 1); // 분할 크기
    int quadrant = calQuadrant(scale, r, c); // 주어진 좌표의 사분면

    int base = unit * quadrant; // 현재 사분면의 시작 번호
    setCoord(scale, r, c); // 좌표 조정

    return base + z(N-1, r, c);
}

int main()
{
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, r, c;
    cin >> N >> r >> c;

    cout << z(N, r, c);
    return 0;
}