[백준] 1074번 Z

문제

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

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2

3 7 7

예제 출력 2

63

 

소스코드

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

int section(int N, int r, int c) {	//	분할 정복을 이용하여 문제를 해결하기 위한 함수이다. 4개의 영역을 각각 1,2,3,4 사분면으로 나누고 재귀를 이용했다.
    int size=1<<(N-1);
    
    if(N==0) {	//개수가 1이 되면 1을 리턴한다.(처음 값)
        return 1;
    }
    if(r<size) {
        if(c<size) return section(N-1, r, c);	//2사분면
        else return size*size+section(N-1, r, c-size);	//1사분면
    } else {
        if(c<size) return size*size*2+section(N-1, r-size, c);	//3사분면
        else return size*size*3+section(N-1, r-size, c-size);	//4사분면
    }
}

int main() {
    int N, r, c;
    
    cin>>N>>r>>c;
    
    cout<<section(N, r, c)-1<<endl;	//0부터 시작하므로 section 함수에서 1을 빼준다.
        
    return 0;
}

찾고자 하는 좌표가 어느 사분면에 있는지 찾고, 해당 사분면을 다시 4등분하여 범위를 좁혀나갑니다.

위 과정을 수행하기 위해 각 사분면의 재귀함수를 호출하고, 좌표가 몇번째인지 리턴합니다.