[재귀/분할정복] 1074번 Z

재귀를 활용한 좋은 문제인것 같다.

정사각형을 정해진 순서대로 방문해야 하고 , 어떤 특정 점을 방문했을시 그 점이 몇번만에 방문된건지 출력하면 되는문제.

지금 현재 재귀 함수가 커버하는 사각형 영역을 식별하기 위해서 시작점(x,y)와 그 정사각형의 길이가 필요하다.

8*8에서 방문 순서를 보면

처음에 8*8 정사각형의 Z 그다음 4*4 정사각형의 Z 4개 그다음 2*2 정사각형 16개 1*1 정사각형 64개 이런식으로 재귀호출 해야한다.

DFS문제를 많이 풀다보니까 재귀호출에 대한 이해가 조금은 깊어진것 같다.

근데 단순히 주어진 순서대로 방문만 하는 경우 시간초과가 뜬다. 왜냐하면 정사각형이 최대 15*15의=225의 크기를 가질수 있으므로 엄청나게 많은 재귀 호출을 하게 될수 있다.

그렇기 때문에 현재 재귀호출하고 있는 정사각형의 범위 내에 정답이 있는지 없는지 판단해서 없다고 판단되는 경우 아예 그 정사각형 영역은 재귀호출하지 않고 리턴시켜 버리며, 그 정사각형 영역에 포함된 점의 개수를 결과값에 더해준다.

(실제 재귀 호출로 방문하지 않지만 방문 했다고 판단하는것임)

소스 코드

#include <iostream>

#include <algorithm>

#include <math.h>

using namespace std;

int n,r,c;

int result;

void recursion(int x,int y,int len){

    if(x==r && y==c){

        cout<<result<<endl;

        exit(0);

    }

    if(len==1){

        result++;return;

    }

    if(!(x<=r && r<x+len && y<=c && c<y+len)){

        result += len*len;

        return;

    }

    recursion(x,y,len/2);

    recursion(x,y+len/2,len/2);

    recursion(x+len/2,y,len/2);

    recursion(x+len/2,y+len/2,len/2);

}

int main(){

    cin>>n>>r>>c;

    

    recursion(0,0,pow(2,n));

    

    return 0;

}