[백준] 숨바꼭질 | 1697 | C++
Algorithm/문제풀이
2022. 8. 20. 00:43
풀이의 핵심은 BFS이다.
필자는 배열 안에 걸린시간을 저장하는 방식으로 풀었다.
#include<bits/stdc++.h>
using namespace std;
int n, k;
int arr[100004];
queue<int> Q;
void BFS() {
while(!Q.empty()) {
int x=Q.front();
Q.pop();
if(x==k) return;
if(x-1>=0 && x-1<=100000 && arr[x-1]==0)
{arr[x-1]=arr[x]+1; Q.push(x-1);}
if(x+1>=0 && x+1<=100000 && arr[x+1]==0)
{arr[x+1]=arr[x]+1; Q.push(x+1);}
if(x*2>=0 && x*2<=100000 && arr[x*2]==0)
{arr[x*2]=arr[x]+1; Q.push(x*2);}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin>>n>>k;
arr[n]=1;
Q.push(n);
BFS();
cout<<arr[k]-1;
return 0;
}
'Algorithm > 문제풀이' 카테고리의 다른 글
[백준] 1463 | 1로 만들기 | C++ (0) | 2022.09.03 |
---|---|
[백준] 16198 | 에너지 모으기 | C++ (0) | 2022.09.03 |
[백준] 12865 | 평범한 배낭 | C++ (0) | 2022.08.17 |
[백준] 14501 | 퇴사 | C++ (0) | 2022.07.21 |
[백준] 17478 | 재귀함수가 뭔가요? | C++ (0) | 2022.07.20 |