BOJ13549: 숨바꼭질 3 작성일 2021-02-15 https://www.acmicpc.net/problem/13549 0-1 BFS라고 덱을 쓰는 BFS를 처음 봤다. 근데 0-1으로 풀면 덱에 최소거리를 저장해야 해서 불편한듯 그냥 BFS로 레벨 고려해가면서 집어넣는게 편하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include <bits/stdc++.h> using namespace std; class Graph { int A, B, sz, depth = 0, zero = 0; vector<int> visit; queue<int> q; public: void input() { cin >> A >> B; visit.resize(200001); if(A == 0) zero = 1, A = 1; } bool travelPow2(int n) { for (int i = n; i > 0; i /= 2) { if(i == A) return true; if(visit[i]) return false; q.push(i); visit[i] = 1; if(i % 2) break; } return false; } int bfs() { if (A >= B) return A - B + zero; if (travelPow2(B)) return 0 + zero; while(q.size()) { depth++, sz = q.size(); for(int s = 0; s < sz; s++) { int cur = q.front(); q.pop(); if (travelPow2(cur+1)) return depth + zero; if (travelPow2(cur-1)) return depth + zero; } } throw std::invalid_argument( "Not Reachable" ); } }; int main() { Graph g; g.input(); cout << g.bfs(); }