백준 1697//숨바꼭질

 

https://www.acmicpc.net/problem/1697

 

 

 

• BFS를 사용: 현재 위치에서 이동 가능한 모든 경우를 큐에 넣고, 가장 먼저 동생의 위치 KKK에 도달하면 그 시간을 반환합니다.
• 방문 여부 확인: 이미 방문한 위치를 다시 방문하지 않도록 방문 여부를 체크합니다.
• 범위 제한: 문제 조건에 따라 0≤X≤100,0000 \leq X \leq 100,0000≤X≤100,000 범위 내에서만 이동을 고려합니다.

 

 

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

int FindfastetPath(int n, int k)
{
	const int MAX = 100000;
	queue<pair<int, int>> now;
	vector<bool> visited(MAX+1, false);
	now.push({ n, 0 });
	visited[n] = true;

	while (!now.empty())
	{
		int current = now.front().first;
		int time = now.front().second;
		now.pop();

		if (current == k) return time;

		if (current - 1 >= 0 && !visited[current - 1])
		{
			
			now.push({ current - 1, time + 1 });
			visited[current - 1] = true;
		}
		if (current + 1 <= MAX && !visited[current + 1])
		{
			now.push({ current + 1, time + 1 });
			visited[current + 1] = true;
		}
		if (current * 2 <= MAX && !visited[current * 2])
		{
			now.push({ current * 2, time + 1 });
			visited[current * 2] = true;
		}
	}
	return -1;//만약 K에 도달하지 못하면...
}

int main()
{
	int n, k;
	cin >> n >> k;

	cout << FindfastetPath(n, k) << endl;

	return 0;

}