[BOJ] 1074 : Z (코드개선) - travelbeeee

문제 : https://www.acmicpc.net/problem/1074

기존 코드 : https://travelbeeee.tistory.com/297

---

 기존 코드에서는 무조건 4등분으로 영역을 분할해 나가면서 모든 경우에 대해서 재귀함수를 통해 탐색했습니다. 하지만, 우리는 답이 있는 영역만 탐색해보면 되므로 if 문을 통해 다음과 같이 쓸데없는 탐색을 줄일 수 있습니다.

#include<iostream>
#include<cmath>
using namespace std;

int N, r, c;

void visit(int x, int y, int length, int i) {
	if (length == 2) {
		if (x == r && y == c)
			cout << i;
		else if (x == r && y + 1 == c)
			cout << i + 1;
		else if (x + 1 == r && y == c)
			cout << i + 2;
		else if (x + 1 == r && y + 1 == c)
			cout << i + 3;
		return;
	}

	int j = length / 2;
	if (x <= r && r < x + j && y <= c && c < y + j)
		visit(x, y, j, i);
	else if(x <= r && r < x + j && y + j <= c && c < y + 2 *j)
		visit(x, y + j, j, i + j * j);
	else if(x + j <= r && r < x + 2 * j && y <= c && c < y + j)
		visit(x + j, y, j, i + 2 * j * j);
	else
		visit(x + j, y + j, j, i + 3 * j * j);
	return;
}

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

	cin >> N >> r >> c;
	int L = int(pow(2, N));
	visit(0, 0, L, 0);
}

---