백준1074 - Z

https://www.acmicpc.net/status?user_id=hsu2016&problem_id=1074&from_mine=1

채점 현황

재귀호출과 분할정복을 활용하여 푸는 문제다. 현재 사각형에서 절반 길이를 나누어 1 -> 2 -> 3 -> 4분면을 탐색하도록 하고 원하는 좌표 위치에 도달하기 전까지 cnt를 1씩 증가시킨다. 원하는 좌표를 찾으면 flag변수를 두어 더이상 재귀호출이 일어나지 않도록 한다.

 

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

int n, r, c; //n은 변의 길이를 2^n으로 표현하기 위하여 사용, r과 c는 (r, c)를 나타낸다.
int cnt = 0; //(r, c)의 값
int flag = false; //flag 변수를 두어 원하는 좌표를 찾으면 더이상 재귀 호출이 일어나지 않도록 한다.

void search(int len, int x, int y) {
	if (flag == true) {
		return;
	}
	if (len == 2) { //최소 단위 사분면의 크기는 2 * 2
		if (x == r && y == c) { //1사분면
			flag = true;
			return;
		}
		cnt++;
		if (x == r && y + 1 == c) { //2사분면
			flag = true;
			return;
		}
		cnt++;
		if (x + 1 == r && y == c) { //3사분면
			flag = true;
			return;
		}
		cnt++;
		if (x + 1 == r && y + 1 == c) { //4사분면
			flag = true;
			return;
		}
		cnt++;
		return; //못찾은 경우
	}
	search(len / 2, x, y); //현재 사각형에서 절반 길이의 1사분면 탐색
	search(len / 2, x, y + len / 2); //현재 사각형에서 절반 길이의 2사분면 탐색
	search(len / 2, x + len / 2, y); //현재 사각형에서 절반 길이의 3사분면 탐색
	search(len / 2, x + len / 2, y + len / 2); //현재 사각형에서 절반 길이의 4사분면 탐색
}

int main() {
	cin >> n >> r >> c;
	n = pow(2, n); //사각형 한 변의 길이는 2^n으로 결정
	search(n, 0, 0);
	cout << cnt;
}