백준 16953번 A->B (C++)

출처: https://www.acmicpc.net/problem/16953

bfs로 문제를 해결하였다.

초기 cnt=1

처음 큐에 pair로 (A, cnt)을 넣고 (A * 2, cnt + 1) 와 (A * 10 + 1, cnt + 1)을 bfs로 탐색하면서 A의 값이 B의 값과 같아지면 cnt를 출력하는 방식으로 해결하였다.

같은 숫자를 또 방문하는 것을 방지하기 위해 탐색 시간 복잡도가 O(1)인 unordered_set에 방문한 값을 넣어줘서 중복을 방지하고, A * 2나 A * 10 + 1이 B보다 커지면 큐에 넣지 않는 식으로 구현하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_set>

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	ll a, b;
	cin >> a >> b;
	queue<pair<ll, ll>> q;
	unordered_set<ll> us;
	q.push({ a,1 });
	us.insert(a);
	ll ans = -1;
	while (!q.empty()) {
		auto a = q.front();
		if (a.first == b) {
			ans = a.second;
			break;
		}
		q.pop();
		if (us.find(a.first * 2) == us.end() && a.first * 2 <= b) {
			q.push({ a.first * 2,a.second + 1 });
			us.insert(a.first * 2);
		}
		if (us.find(a.first * 10 + 1) == us.end() && a.first * 10 + 1 <= b) {
			q.push({ a.first * 10 + 1,a.second + 1 });
			us.insert(a.first * 10 + 1);
		}
	}
	cout << ans;
};