cote/Intermediate
백준 1697//숨바꼭질
geminanolja
2025. 1. 21. 16:46
https://www.acmicpc.net/problem/1697
- BFS를 사용: 현재 위치에서 이동 가능한 모든 경우를 큐에 넣고, 가장 먼저 동생의 위치 KK에 도달하면 그 시간을 반환합니다.
- 방문 여부 확인: 이미 방문한 위치를 다시 방문하지 않도록 방문 여부를 체크합니다.
- 범위 제한: 문제 조건에 따라 0≤X≤100,0000 \leq X \leq 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;
}