1074.Z

이번에 풀어볼 문제는 백준의 Z이다. 재귀함수를 이용하여 탐색을 하는 문제인데

재귀함수를 잘 활용해야 풀 수 있는 문제이다. 개인적으로 쉬워보이지만 난이도가 상당하다고 느꼈다.

이런 문제를 잘풀어야하는데.. 흑흑..

1074번: Z

이 문제를 푸는 포인트는 두 가지이다.

1. 재귀함수에서 조건을 통해 굳이 확인할 필요없는 탐색 순번은 그 카운트 만큼 더해주고 넘어가기

2. 4등분해서 탐색하되 크기에 상관없이 이러한 탐색이 진행되도로 재귀함수를 짤 수 있어야 한다

=> 그래서 생각보다 복잡했고.. 결국 못 풀었다..

참고 블로그 : https://simsimjae.tistory.com/191#recentComments

 

 

---

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <math.h>
 
using namespace std;
 
int N, r, c;
int cnt;
 
void search(int x, int y, int len){ // x, y좌표, 한변의 길이
    if (x == r && y == c){   // 우리가 찾는 좌표가 나오면
        cout << cnt << endl; // 지금까지 카운트한 값을 출력하고
        exit(0);             // 종료
    }
    
    if (len == 1){           // 길이가 1이면 2*2짜리에서 탐색을 하는 것이므로
        cnt++;               // 탐색 하나 했으니 카운트 +1;
        return;              // 리턴 후 다음 등분 1 -> 2 -> 3 -> 4사분면 순으로 Z 모양으로 탐색이 진행됨
    }
        
 
    if (!(x <= r && r < x+len && y <= c && c < y+len)){ // x나 y 좌표가 해당 분면 조건을 벗어나는 경우
        cnt += len*len; // 굳이 해당 사분면을 탐색할 필요가 없으므로 해당 사분면의 최대 카운트를 누적하여 탐색한 것으로 침
        return;
    }
 
    search(x,y,len/2);                         // 1사분면
    search(x, y + len / 2, len / 2);           // 2사분면
    search(x + len / 2, y, len / 2);           // 3사분면
    search(x + len / 2, y + len / 2, len / 2); // 4사분면 탐색
}
 
int main() {
    freopen("1074.txt", "r", stdin);
    cin >> N >> r >> c;
    search(0,0, pow(2,N));
    return 0;
}