BOJ 1074, Z

문제

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

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

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

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

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

전형적인 프랙탈도형 문제이다.

큰 칸부터, 차례로 아래처럼

0 1 2 3순으로 방문할 것이므로, 방문 위치(순서)를 계산해주고 3번째 칸에 있다면 (2^n-1)^2 * 3

그 다음, 넓이가 4분의 1인 사각형에 대해서도 4등분해서 방문 위치를 잡아준다.

결국, 2 by 2 칸이 나올 때 까지 재귀적으로 해결해주면 끝!

아래 code의 mapsize[..]은 2^n을 빠르게 계산하기 위해 추가해 준 것이다.

#include <cstdio>
#include <iostream>
 
using namespace std;
 
typedef long long LL;
 
int mapsize[16] = { 1 };
 
int Z(int, int, int);
 
int main() {
    int N, R, C;
    for (int i = 1; i < 16; i++) {
        mapsize[i] = mapsize[i - 1] * 2;
    }
 
    while (scanf("%d %d %d", &N, &R, &C) > 0) {
        printf("%d\n", Z(N, R, C) - 1);
    }
}
 
int Z(int n, int r, int c) {
    if (n == 0) return 1;
 
    if (r < mapsize[n - 1]) {
        if (c < mapsize[n - 1]) return Z(n - 1, r, c);
        else return mapsize[n - 1] * mapsize[n - 1] + Z(n - 1, r, c - mapsize[n - 1]);
    }
    else {
        if (c < mapsize[n - 1]) return mapsize[n - 1] * mapsize[n - 1] * 2 + Z(n - 1, r - mapsize[n - 1], c);
        else return mapsize[n - 1] * mapsize[n - 1] * 3 + Z(n - 1, r - mapsize[n - 1], c - mapsize[n - 1]);
    }
}