[BAEKJOON] 16953

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

[sliver 2, 16953 A→B] - 너비우선탐색(BFS)

10^9자리에서 10^10자리까지 확인할 수 있기 때문에, long long 자료형을 활용해야 하는 것이 핵심이다.

보통 string stl을 사용하면서 숫자를 변환하기 위해 stoi를 많이 활용하는데, 이 함수는 무언가의 약자임을 기억하자.

약자임을 기억한다면, stoi가 string to int임을 생각할 수 있고 다양한 방면으로 연계하여

string을 long long으로 바꾸자 할 때, stoll 함수를 활용할 수 있음을 깨달을 수 있다.

#include <iostream>
#include <string>
#include <queue>
#pragma warning(disable:4996)

using namespace std;

typedef struct data {
	long long n;
	int cnt;
}Data;

int main() {
	long long int st, ed;
	scanf("%lld %lld", &st, &ed);

	queue<Data> q;
	q.push({st, 0});

	while (!q.empty()) {
		Data out = q.front(); q.pop();
		if (out.n == ed) {
			printf("%lld", out.cnt + 1);
			return 0;
		}
		string next = to_string(out.n) + '1';
		long long next1 = stoll(next);
		long long next2 = out.n * 2;
		if (next1 <= ed) {
			q.push({ next1, out.cnt + 1 });
		}
		if (next2 <= ed) {
			q.push({ next2, out.cnt + 1 });
		}
	}
	printf("-1");
}