[백준 C++] 16953 A → B - 너비우선탐색

16953번: A → B

#include <iostream>
#include <string>
#include <queue>
using namespace std;

queue<pair<int, int>> SearchQueue;

int BFS(int Start, int End)
{
	SearchQueue.emplace(Start, 1);
	while (!SearchQueue.empty())
	{
		long long Current = SearchQueue.front().first;
		int Depth = SearchQueue.front().second;
		SearchQueue.pop();

		if (Current == End)
		{
			return Depth;
		}
		else if (Current > End)
		{
			continue;
		}

		long long N1 = 2 * Current;
		if (N1 <= 1000000000)
		{
			SearchQueue.emplace(N1, Depth + 1);
		}

		long long N2 = Current * 10 + 1;
		if (N2 <= 1000000000)
		{
			SearchQueue.emplace(N2, Depth + 1);
		}
	}

	return -1;
}

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

	int A, B;
	cin >> A >> B;

	cout << BFS(A, B);
}

---

 

A 부터 시작해서 두 가지 연산을 수행한 각각의 결과를 통해서 B 까지 이동하는 최소 깊이를 찾아내는 문제입니다.

pair를 이용해서 현재 숫자의 값과 깊이를 저장해서 큐에 추가하도록 했습니다.

그리고 B에 도달했을 경우 해당깊이를 출력해주고 B보다 값이 커지면 탐색을 종료하도록 했습니다.