백준
백준 소스코드 [C++] 1697 숨바꼭질
Hani_Levenshtein
2020. 8. 24. 22:21
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가
www.acmicpc.net
백준 소스코드 [C++] 1697 숨바꼭질
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
int n, m,pp,time=0;
bool check[100001];
queue <int> q, t;
void bfs() {
while (q.empty() != true) {
while (q.empty() != true) {
t.push(q.front());
q.pop();
}
while (t.empty() != true) {
pp = t.front();
if (pp == m) {
cout << time;
return;
}
if (pp-1>=0 && check[pp - 1] == false) {
q.push(pp - 1);
check[pp - 1] = true;
}
if (pp + 1 <= 100000 && check[pp + 1] == false) {
q.push(pp + 1);
check[pp + 1] = true;
}
if (pp*2<=100000 && check[pp * 2] == false) {
q.push(pp * 2);
check[pp * 2] = true;
}
t.pop();
}
time++;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >>m;
q.push(n);
bfs();
return 0;
}