백준
백준 소스코드 [C++] 12851 숨바꼭질 2
Hani_Levenshtein
2020. 10. 22. 00:39
12851번: 숨바꼭질 2
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
www.acmicpc.net
백준 소스코드 [C++] 12851 숨바꼭질 2
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
typedef long long ll;
using namespace std;
int arr[100001];
bool check[100001];
void bfs(int n, int k) {
queue<int> q, t,r;
q.push(n);
int cnt = 0;
arr[n] = 1;
check[n] = true;
while (q.empty() != true) {
while (q.empty() != true) {
t.push(q.front());
q.pop();
}
while (t.empty() != true) {
int temp = t.front();
t.pop();
if (temp == k) {
cout << cnt << '\n' << arr[temp];
return;
}
if ((temp + 1 <= 100000 && arr[temp + 1] == 0)) {
for(int i=0;i<arr[temp];i++)r.push(temp + 1);
if (check[temp + 1] == false) {
q.push(temp + 1);
check[temp + 1] = true;
}
}
if ((0 <= temp - 1 && arr[temp - 1] == 0) ) {
for (int i = 0;i < arr[temp];i++)r.push(temp - 1);
if (check[temp - 1] == false) {
q.push(temp - 1);
check[temp - 1] = true;
}
}
if ((2 * temp <= 100000 && arr[2 * temp] == 0) ) {
for (int i = 0;i < arr[temp];i++)r.push(2 * temp);
if (check[2*temp ] == false) {
q.push(2*temp );
check[2*temp ] = true;
}
}
}
while (r.empty() != true) {
arr[r.front()]++;
r.pop();
}
cnt++;
}
return;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int n, k;
cin >> n >> k;
bfs(n, k);
return 0;
}