[백준 1074] Z

분할정복 문제이다.

"Z" 방향으로 탐색을 하면서, 주어진 좌표가 몇 번째에 탐색이 되는지 출력하는 문제이다.

0 1  

2 3

이라고 하면, 0 -> 1 -> 2 -> 3 순으로 탐색이 되며, 분할 탐색을 해가면서

각 좌표마다 입력 값과 비교하여, 결과를 출력한다.

출처 : https://www.acmicpc.net/problem/1074

문제

한수는 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보다 작거나 같은 정수이다

출력

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

소스코드

#include<iostream>
 
using namespace std;
 
int n,r,c,ans=0;
 
void Z(int x, int y, int size){
    if(size == 2){
        if(y == r && x == c){
            cout << ans;                
            return;
        }
        ans++;
        if((y == r && x+1 == c)){
            cout << ans;
            return;
        }
        ans++;
        if((y+1 == r && x == c)){
            cout << ans;
            return;
        }
        ans++;
        if((y+1 == r && x+1 == c)){
            cout << ans;
            return;
        }
        ans++;
        return;
    }
    Z(x, y, size/2);
    Z(x+size/2,y,size/2);
    Z(x,y+size/2,size/2);
    Z(x+size/2,y+size/2,size/2);
}
int main(){
    cin >> n >> r >> c;
    Z(0,0,1<<n);
    return 0;
}

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.