[백준 1074] Z

우선 방문 번호가 함수 호출 순서라는 것을 알 수 있다.

몇 번째 재귀에 해당 칸을 방문하는지가 해당 칸 번호라는 것이다

 

따라서 해당 방식으로(여기서는 Z) 재귀가 진행되도록 하면 된다.

 

그럼 일단 재귀 문을 간략하게 다음과 같이 짤 수 있다.

void solve(int y, int x, int size){
    size /= 2;
    // Z방식으로 탐색
    solve(y, x, size);
    solve(y, x+size, size);
    solve(y+size, x, size);
    solve(y+size, x+size, size);
}

 

그럼 이제 r c를 만나면 끝나도록 할 수 있는데 초반에 시간초과가 떴다.

이유는 찾고 남은 solve가 있으면 해당 solve들도 다 돌고 끝나기 때문

 

1번의 예시를 들면 다음과 같다

 

만약 2번째 solve(y, x+size, size) 에서 끝났으면 바로 남은 3 4번째 재귀를 돌지 않고 바로 나와야하는데

해당 재귀들도 모두 돌고 있기 때문이다.

그래서 찾았으면 flag=true로 만들고 다른 재귀를 들어갔을때 하위 재귀를 탐색하지 않고 바로 빠져나올 수 있게 함.

 

그리고 하위 재귀도 돌면 cnt값이 그에 따라 증가해 어떤 경우는 오답이 출력된다.

 

방법의 차이도 있다

나는 cnt 값을 사용해 solve 전체가 끝나면 출력하게 했는데

그냥 찾으면 출력하고 하위 재귀를 걍 다 돌게 냅둬도 통과는 되었다.

 

---

#include <iostream>
#include <cmath>

using namespace std;

int** board;
int cnt, r, c;
bool flag;

void solve(int starty, int startx, int size) {
	if (flag) return;

	// 찾았으면
	if (starty == r && startx == c) {
		flag = true;
	}
	// 해당 정사각형 내부에 있으면
	else if (r >= starty && r < starty + size && c >= startx && c < startx + size) {
		// Z 방식으로 탐색
		size /= 2;
		solve(starty, startx, size);
		solve(starty, startx + size, size);
		solve(starty + size, startx, size);
		solve(starty + size, startx + size, size);
	}
	else{
		cnt += size * size;
	}
	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	flag = false;
	cnt = 0;
	int N;
	cin >> N >> r >> c;

	board = new int* [N];
	for (int i = 0; i < N; i++) {
		board[i] = new int[N];
	}

	solve(0, 0, pow(2, N));
	cout << cnt;
	return 0;
}

 

#include <iostream>
#include <cmath>

using namespace std;

int N, r, c;

// r행 c열
int result = 0;

void Z(int y, int x, int size)
{
    if (y == r && x == c)
    {
        cout << result << "\n";
        return;
    }

    // r,c 가 현재 사분면에 존재할때
    if (r < y + size && r >= y && c < x + size && c >= x)
    {
        Z(y, x, size / 2);
        Z(y, x + size / 2, size / 2);
        Z(y + size / 2, x, size / 2);
        Z(y + size / 2, x + size / 2, size / 2);
    }
    else
    {
        result += size * size;
    }
}

int main(void)  
{
    int n = 0;
    cin >> N >> r >> c;
    n = pow(2, N);
    Z(0, 0, n);
    return 0;
}