[BOJ] 16953 : A → B

Question

---

Solution

• 첫 시작 지점 a를 큐에 넣고 두 가지의 연산으로 b에 도달할 수 있는지 탐색하면 되는 간단한 문제이다.

---

Cord

#include <iostream>
#include <queue>

using namespace std;

long long a, b;

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

int bfs(long long _start, long long _cnt)
{
	q.push({ _start, _cnt });

	while (!q.empty())
	{
		long long current = q.front().first;
		long long cnt = q.front().second;
		q.pop();
		
		if (current == b)
		{
			return cnt;
		}
		if (current * 2 <= b)
		{
			q.push({ current * 2, cnt + 1 });	
		}
		if (current * 10 + 1 <= b)
		{
			q.push({ current * 10 + 1, cnt + 1});
		}  
	}

	return -1;
}

int main()
{
	cin >> a >> b;

	cout << bfs(a, 1);

	return 0;
}

---

Result