[C++][백준] 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열을 몇 번째로 방문했는지 출력한다.

 

처음에는 2^15인 2차원 배열을 만든 다음 재귀 함수를 돌려 순차적으로 채워나가는 것을 생각해봤다.
그렇지만 시간제한이 0.5초이었기 때문에 배열을 전부 만든 다음 인덱스를 찾아 값을 불러오면 반드시 시간초과가 나올 것이라는 생각이 들었다.

 

그래서 생각한 것이 r,c위치의 숫자 범위로 좁혀나가 수를 특정하는 방법이다.

코드를 살펴보자

#include <bits/stdc++.h>
using namespace std;
int N,r,c;


void Zee(long long size,long long x, long long y, long long num)
{
    if(size == 2) { //종료조건
        if(c==x)
        {
            if(r==y)
                cout << num;
            else
                cout << num+2;
        }
        else{
            if(r==y)
                cout << num+1;
            else
                cout << num+3;
            }
        return;
    }
    size = size/2;
    if(c< x+size)
    {
        if(r < y+size)
            Zee(size, x, y, num); // 2사분면
        else
            Zee(size,x,y+size,num+size*size*2); // 3사분면
    }
    else{
        if(r<y+size)
            Zee(size,x+size,y,num+size*size); // 1사분면
        else
            Zee(size,x+size,y+size,num+size*size*3); // 4사분면
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> r >> c;
    long long size;
    size = (long long)pow(2,N);
    Zee(size,0,0,0);
    return 0;
}

• 함수에서 우리는 각 사분면에서의 왼쪽 위의 인덱스와 그 값을 인자로 넘겨줄 수 있다.
• 그리고 N의 값을 알기 때문에 특정 단계에서 4등분 했을 때의 각 사각형의 왼쪽 위 값을 계산할 수 있다.
• 그러므로 r,c가 해당되는 사분면을 특정할 수 있고 조건문을 이용해 재귀를 돌릴 수 있다.
• 재귀함수의 종료조건은 다음과 같다.
• size가 2인 4칸짜리 사각형 상태가 되면 r,c가 해당하는 위치의 숫자를 반환한다.