[BOJ] 16953 : A -> B - travelbeeee

문제 : https://www.acmicpc.net/problem/16953

---

BFS

 A에서 BFS 탐색을 진행하면 되는데, 범위가 10^9로 check 배열을 따로 만들 수 없다. 하지만, 항상 증가하는 방향으로 숫자가 변하기 때문에 사이클이 생길 수 없으므로 그냥 BFS 탐색을 진행하면 된다.

#include<iostream>
#include<queue>

using namespace std;

long long A, B;
queue<pair<long long, int>> q;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> A >> B;

	q.push({ A, 0 });
	while (!q.empty()) {
		pair<long long, int> cur = q.front(); q.pop();
		if (cur.first == B) {
			cout << cur.second + 1 << '\n';
			return 0;
		}
		if (cur.first * 2 <= B){
			q.push({ cur.first * 2, cur.second + 1 });
		}
		if (cur.first * 10 + 1 <= B) {
			q.push({ cur.first * 10 + 1, cur.second + 1 });
		}
	}
	cout << -1;
	return 0;
}

---