백준 16953 A → B (c++) : 피너클

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

16953번: A → B

bfs문제다.

이번에는 bool로 이전에 나온적이 있는 숫자인지를 확인할필요가 없다.

A * 2를 하거나 A * 10 + 1을 하거나 둘중 하나를 하는것이기에 숫자가 겹치는 경우가 없다.

cin >> a >> b;
queue<pair<long, long>> q;
q.push({ a, 0 });
int ans = -1;

값을 입력받고 q를 선언한다. q에는 {현재 숫자, 연산 횟수}를 넣을것이다.

while (!q.empty()) {
	long now = q.front().first;
	long time = q.front().second;
	q.pop();
	if (now > b) continue;

now는 현재 숫자, time은 현재 숫자까지의 연산 횟수를 의미한다.

만약 now가 b보다 크다면 뒤의 연산을 할 필요가 없으니 continue로 다 무시한다.

	if (now == b) {
		ans = time + 1;
		break;
	}

만약 현재 숫자가 b와 같다면 ans에 time + 1을 넣고 반복문에서 나온다.

	q.push({ now * 2, time + 1 });
	q.push({ now * 10 + 1, time + 1 });
}

그후 q에 now * 2와 now * 10 + 1을 넣는다.

cout << ans << endl;

마지막으로 ans를 출력한다.

#include <iostream>
#include <queue>

using namespace std;

long a, b;

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

	cin >> a >> b;
	queue<pair<long, long>> q;
	q.push({ a, 0 });
	int ans = -1;
	while (!q.empty()) {
		long now = q.front().first;
		long time = q.front().second;
		q.pop();
		if (now > b) continue;

		if (now == b) {
			ans = time + 1;
			break;
		}
		q.push({ now * 2, time + 1 });
		q.push({ now * 10 + 1, time + 1 });
	}
	cout << ans << endl;
}

전체코드다.