[백준/c++] 1697 숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

구현해야할 조건

BFS이동으로 생각해서 문제를 해결하면 되는데, x+1, x-1, x*2에 관한 이동을 하면 된다. 단 x-1 >= 0과 같은 범위를 꼭 지정해주어야 범위를 벗어나지 않는다. n과 k는 정수이기 때문에! 

 

#include<iostream>
#include<queue>

#define MAX 100001
using namespace std;

bool visited[MAX];

int BFS(int n, int k)
{
	queue<pair<int,int> > q;
	q.push({n,0});
	
	visited[n] = true;
	
	while(!q.empty())
	{
		int location = q.front().first;
		int sec = q.front().second;
		q.pop();
		
		if(location == k)
			return sec;
			
		if(location + 1 < MAX && !visited[location+1]) // x + 1 < MAX
		{
			q.push({location+1, sec+1});
			visited[location+1] = true;
		}
		
		if(location - 1 >= 0 && !visited[location - 1]) // x - 1 >= 0
		{
			q.push({location - 1, sec+1});
			visited[location - 1] = true;
		}
		
		if(location * 2 < MAX && !visited[location * 2]) // x * 2 < MAX
		{
			q.push({location * 2, sec + 1});
			visited[location*2] = true;
		}
	}
	
}

int main()
{
	int n,k;
	cin >> n >> k;
	
	cout << BFS(n,k) << "\n";
	
	return 0;
}