4112. 이상한 피라미드 탐험

출처

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

 

 

 

 

 

BFS로 구현 하였으나 답은 잘 나오는데 1000개의 테스트 케이스에서 시간초과가 발생하였다.

하지만 이 문제는 BFS가 아닌 일반 로직을 구현해서 풀 수 있었다.

 

시작점이 종료지점보다 위에 존재하는 경우 

1) 시작점의 x좌표가 종료점의 x좌표보다 작거나 같다.

2) 시작점의 x좌표가 종료점의 x좌표보다 크다.

시작점이 종료지점보다 아래에 존재하는 경우

1) 시작점의 x좌표가 종료점의 x좌표보다 크거나 같다.

2) 시작점의 x좌표가 종료점의 x좌표보다 작다.

 

기본적으로 각 케이스의 1번 같은 경우는 시작점과 종료점의 x좌표 차이와 y좌표 차이중 큰 값만큼 시간이 소비된다.

하지만 각 2번의 경우에는 x좌표와 y좌표의 차이중 큰 값에 차이중 작은 값 만큼의 합이 더 추가된 시간 만큼 소비된다.

따라서 기본적으로 더해지는 변수 addNum 을 0으로 잡고 2번 케이스인 경우에 min값을 addNum에 입력시켜 준다.

예외가 아닌 경우는 0이 그대로 더 해 질것이고 예외인 케이스에만 addNum에 값이 추가로 입력되어 더해진다.

 

<코드>

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





int main(void)
{

	int N;
	cin >> N;
	
	for(int tc = 1; tc <= N; tc++)
	{
		
		int sx, sy;
		int ex, ey;
		int sum = 0;
		
		int a,b;
		cin >> a >> b;
		
		int temp1 = a;
		int temp2 = b;
		
		int idx;
	
		
		for(int i = 1; i <=10000; i++)
		{
		
			sum += i; 
		
			temp1 -= i;
			if(temp1 <= 0)
			{
				idx = i;
				
				sx = a - (sum-(i-1));	
				sy = i;
				
			
				break;
				
			}
		
		}
		sum = 0;
		for(int i = 1; i <=10000; i++)
		{
		
			sum += i; 
		
			temp2 -= i;
			if(temp2 <= 0)
			{
				idx = i;
			
				ex = b - (sum-(i-1));	
				ey = i;
		
				
				break;
				
			}
		
		}
		
		
		int addnum = 0;
	 
		int ydiff = abs(sy-ey);
		int xdiff = abs(sx-ex);
		
		
		
		if((ex<sx && sy<ey) || (sy>ey && sx<ex))
		{
			addnum = min(ydiff,xdiff);
		}
		
		if(xdiff < ydiff)
		{
			cout << "#"<<tc<<" "<<ydiff+addnum<<endl;
			
		}
		else
		{
			cout<<"#"<<tc<<" "<<xdiff+addnum<<endl;
		}
		
		
		
	}
	
	
	
	return 0;
}

 

 

 

 

 

 

 

<BFS 코드>

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




bool visit[143][143];


struct Node{
	
	
	int sy;
	int sx;
	
	int count;
};

int main(void)
{

	int N;
	cin >> N;
	
	for(int tc = 1; tc <= N; tc++)
	{
		
		int sx, sy;
		int ex, ey;
		int sum = 0;
		
		int a,b;
		cin >> a >> b;
		
		int temp1 = a;
		int temp2 = b;
		
		int idx;
		
		for(int i = 1; i <= 142; i++)
		{
			for(int j =1; j<=142; j++)
			{
				visit[i][j] = false;
			}
		}
		
		
		for(int i = 1; i <=10000; i++)
		{
		
			sum += i; 
		
			temp1 -= i;
			if(temp1 <= 0)
			{
				idx = i;
				
				sx = a - (sum-(i-1));	
				sy = i;
				
			
				break;
				
			}
		
		}
		sum = 0;
		for(int i = 1; i <=10000; i++)
		{
		
			sum += i; 
		
			temp2 -= i;
			if(temp2 <= 0)
			{
				idx = i;
			
				ex = b - (sum-(i-1));	
				ey = i;
		
				
				break;
				
			}
		
		}
		
		
		
		queue<Node> que;
		
		que.push({sy,sx,0});
		
		visit[sy][sx] = true;
		
		while(!que.empty())
		{
			
			int y = que.front().sy;
			int x = que.front().sx;
			
			int count = que.front().count;
			
			que.pop();
			
			
			if(x==ex && y==ey)
			{
				cout<<"#"<<tc<<" "<<count<<endl;
				break;
				
			}			
			
			if(y <= ey && (y != ey))
			{
				if(ex <= x )
				{
				
					que.push({y+1,x,count+1});
				}
				else
				{
					
						
						que.push({y+1,x+1,count+1});
					
				
				}
				
				
			}
			else if(y <= ey && (y == ey))
			{
				if(x <= sx)
				{
				
						que.push({y,x-1,count+1});
						
					
				
				}
				else
				{
					
						que.push({y,x+1,count+1});
						
					
				
				}
				
			}
			else if(ey < y && (y != ey) )
			{
				
				if(ex < x)
				{
					
						que.push({y-1,x-1,count+1});
					
				
				}
				else
				{
				
				
						que.push({y-1,x,count+1});
					
					
				}
				
				
			}
			else if(ey < y && (y == ey) )
			{
				
				if(ex <= x)
				{
					
					
						que.push({y,x-1,count+1});
					
					
				}
				else
				{
				
						que.push({y,x+1,count+1});
					
					
				}
				
				
			}
			
			
			
			
			
		}
		
		
		
		
		
	 
		
		
		
		
	}
	
	
	
	return 0;
}