[백준 1074번] Z ( 분할정복, 재귀) ** 다시풀어보기**

처음 분할정복 / 재귀 문제를 풀어보는데,

애초에 이게 분할정복인지 재귀인지 모르고 풀었다.

dfs로 풀 수 있을것 같아서 풀어봤었는데 역시 시간초과.

2시간 가량 생각해서 풀었는데..

 

분할정복 개념은 알고있었지만 이것에 대한 문제를 풀어본 적이 없어서 너무너무 헷갈렸다.

 

그래서 다른사람들의 블로그를 참고해서 다시 풀어보기로 한다.

 

아래는 처음 구현했던 코드다 아주 난잡하기 짝이없다.

#include <bits/stdc++.h>

using namespace std;
int N,r,c;
int cnt = 0;
void dfs(int row, int col, int d,int sx, int sy)
{   
    if(d >= pow(2,N-1)*pow(2,N-1)) return;
    
    if(r == row && c == col ) cout <<  cnt <<endl;
    cnt++;
    
    int mod = d%4;
    switch(mod){
        case 0:
            dfs(row,col+1,d+1,sx,sy);
            break;
        case 1:
            dfs(row+1,col-1,d+1,sx,sy);
            break;
        case 2:
            dfs(row,col+1,d+1,sx,sy);
            break;
        case 3:
            
            if((d+1)%((int)pow(2,N-1)*2) ==0 ){
                dfs(row+1, sy,d+1,sx,sy);
            }else{
                dfs(row-1, col+1,d+1,sx,sy);
            }
            break;
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> r >> c;

    if( (r>=0 && r<pow(2,N-1)) && (c >=0 && c < pow(2,N-1)) )
    {
        cnt = 0;
        dfs(0,0,0,0,0);
    }
    else if((r >=0 && r<pow(2,N-1)) && (c>= pow(2,N-1) && c< pow(2,N) )){
        cnt = pow(2,N-1)*pow(2,N-1);
        dfs(0,pow(2,N-1),0,0,pow(2,N-1));
    }
    else if((r>=pow(2,N-1) && r< pow(2,N)) && (c >=0 && c < pow(2,N-1)))
    {
        cnt = pow(2,N-1)*pow(2,N-1)*2;
        dfs(pow(2,N-1),0,0,pow(2,N-1),0);
    }
    else if((r>=pow(2,N-1) && r<pow(2,N)) && (c>=pow(2,N-1) && c < pow(2,N)))
    {
        cnt = pow(2,N-1)*pow(2,N-1)*3;
        dfs(pow(2,N-1), pow(2,N-1),0,pow(2,N-1),pow(2,N-1));
    }
    
    
}

 

---

#include <bits/stdc++.h>

using namespace std;
int N,r,c;
int cnt = 0;
bool flag = 1;
void dfs(int row, int col , int size)
{
    //dfs 탐색순서 = 왼쪽 위 , 오른쪽 위 , 왼쪽 아래, 오른쪽 아래.
    //자신의 범위 안에 없으면 return.
    if(row ==r && col == c) {
        flag =0;
        return;
    }
    if( r>=row && r<row+pow(2,size) && c >= col && c <col+pow(2,size))
    {
        if(flag)dfs(row, col, size-1); //왼쪽 위
        if(flag)dfs(row,col+pow(2,size-1),size-1); // 오른쪽 위
        if(flag)dfs(row+pow(2,size-1),col, size-1); // 왼쪽 아래
        if(flag)dfs(row+pow(2,size-1), col+pow(2,size-1), size-1); // 오른쪽 아래.
        
    }else{
        cnt+= pow(2,size)*pow(2,size);
        return;
    }

}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> r >> c;
    
    dfs(0,0,N);
    cout << cnt << endl;
}

재귀를 쓰면 참 머리가 아픈데,  코드가 간결해지는걸 보면 신기하다.

 

일단 아이디어는 아래와 같다.

 

4개의 dfs를 사용하여 구간을 정하여 (왼쪽위 / 오른쪽 위 / 왼쪽 아래 / 오른쪽 아래 순서 'Z모양') 재귀를 실행한다.

만약 타겟 좌표가 제일 오른쪽 아래라면 무슨일이 벌어질까.

ex) N = 3, r = 7,  c = 7이라면 8x8보드에서 오른쪽 아래에 타겟이 위치하게 된다. (아래 그림 참조)

이때 저 dfs문을 실행하게 되면 맨처음에는 8x8보드 전체에서 어느 사분면에 위치하는지를 위에 정해진 구간에 따라 실행하게 된다.

왼쪽 위, 오른쪽 위, 왼쪽 아래 (dfs 1,2,3번째 code)를 실행하면 (r,c)가 해당 범위에 없기때문에 그 구간의 칸수를 구하여 count 값에 더해주고 빠져나온다.

 

오른쪽 아래를 실행하게 되면 해당 범위 내 이므로 다시 그 구간을 4개로 나누어 dfs를 실행하게 되며 동일하게 dfs 1,2,3번쨰 코드는 해당 구간의 칸수를 구하여 더해주고 return되며, 마지막으로 N=0일때까지 실행하게 되면 최종 cnt가 계산된다.