백준 1074번 : Z

문제 접근

---

처음에는 Z 형태로 탐색하다가 해당 좌표가 (r,c) 면 cnt 반환하는 방식으로 풀었고, 시간초과가 나자 4분면으로 나눠 필요한 부분만 탐색하도록 했다.

 

오류

---

(r,c) 를 찾았는데 계속 탐색을 이어가며 cnt가 증가됐다. 처음에는 return; 해도 안 끝나나 싶어서 24행에 cout<<"?\n"; 으로 확인해봤는데, return; 이후 '?' 가 출력되지 않는 걸로 봤을때 아니라고 생각했다. 그 다음으로 생각해보니 recursive 를 종료해도 재귀 호출한 recursive 를 실행하기에 계속 탐색한다고 생각했다. 그래서 bool isFind 라는 변수를 만들어서 (r,c)를 찾지 못할때만 탐색하도록 했더니 잘 종료됐다. 근데 시간 초과 나온다 ㅠㅠㅠ.

 

N 이 클 경우 하나하나 탐색하는데 오래 걸려서 시간초과 나올 수 있다고 생각했다. N =15 일때, 최악의 경우 recursive() 가 4^15번 호출된다. 그래서 기존의 탐색을 건너뛸 수 있는 방법을 생각해봤는데 4분면으로 접근하면 좋을 것 같았다. 확인할 좌표는 아니까 이걸 length 에 따라 계속 비교해주고 어떤 부분에 있는지 확인한 뒤 cnt 에 건너뛴 범위를 추가하는 방식이다. 예제 case 에는 잘 나왔다.

 

문제 풀이 (확인용) - 탐색 : 시간초과

---

#include <iostream>
#include <cmath>

using namespace std;

int dx[4] = {0,0,1,0};
int dy[4] = {0,1,-1,1};
int N,r,c,cnt=-1;

void recursive(int length, int x, int y)
{
	cout<<"recursive("<<length<<", "<<x<<", "<<y<<")\n";
		
	if(length == 1)
	{
		cnt++;
		
		if(x==r && y==c)
		{
			cout<<"Find it!!! -> "<<cnt<<'\n';
			return;
		}
		
		cout<<"?\n";
	}
	
	else
	{
		for(int i=0; i<4; ++i)
		{
			x += length/2 * dx[i%4];
			y += length/2 * dy[i%4];

			recursive(length/2,x,y);
		}
	}
}

int main(void)
{
	cin>>N>>r>>c;
	recursive(pow(2,N),0,0);
	
	cout<<cnt<<'\n';
	
	return 0;
}

예제 case 제출 결과

 

 

문제 풀이 (제출용) - 탐색 : 시간초과

---

#include <iostream>
#include <cmath>

using namespace std;

int dx[4] = {0,0,1,0};
int dy[4] = {0,1,-1,1};
int N,r,c,cnt=-1;
bool isFind=false;

void recursive(int length, int x, int y)
{
	if(length == 1)
	{
		cnt++;
		
		if(x==r && y==c)
			isFind=true;
	}
	
	else
	{
		for(int i=0; i<4; ++i)
		{
			x += length/2 * dx[i%4];
			y += length/2 * dy[i%4];
			
			if(!isFind)
				recursive(length/2,x,y);
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin>>N>>r>>c;
	recursive(pow(2,N),0,0);
	
	cout<<cnt<<'\n';
	
	return 0;
}

예제 case 실행 결과

 

문제 풀이 - 4분면 : 맞았습니닭!

---

#include <iostream>
#include <cmath>

using namespace std;

int dx[4] = {0,0,1,1};
int dy[4] = {0,1,0,1};
int N,r,c,cnt=0;
bool isFind=false;

int check_div(int length,int x,int y)
{
	if(r<x+length)
	{
		if(c<y+length)
			return 0;
		else
			return 1;
	}
	
	else
	{
		if(c<y+length)
			return 2;
		else
			return 3;
	}
}

void recursive(int length, int x, int y)
{
	if(length==1)
		return;
	
	int div=check_div(length/2,x,y);
	x += length/2 * dx[div];
	y += length/2 * dy[div];
		
	cnt+=pow(length/2,2)*div;
	//cout<<"Length : "<<length<<" Div : "<<div+1<<" cord("<<x<<","<<y<<") -> "<<cnt<<'\n';
	recursive(length/2,x,y);
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin>>N>>r>>c;
	recursive(pow(2,N),0,0);
	
	cout<<cnt<<'\n';
	
	return 0;
}

예제 case 실행 결과

결과

---