16953 A → B

BFS, DFS로도 풀 수 있는 문제다. DFS는 BFS에 비해 코드가 직관적이고 길이가 짧은게 장점이지만 디버깅이 어렵고 기저사례를 잘 지정해줘야한다.

두 방식을 연습해봐야겠다.

BFS 정답코드

#include <iostream>
#include <queue>
using namespace std;
long long A, B;
long long nextNum(long long i, long long num)
{
	switch (i)
	{
	case 0:
		return num * 2;
	case 1:
		return num * 10 + 1;
	}
}
int main()
{
	cin >> A >> B;
	if (A == B) {
		printf("0\n");
		return 0;
	}
	queue<pair<long long, long long>> q;
	q.push({ A, 0 });
	long long next = 0;
	while (!q.empty()) {
		long long num = q.front().first;
		long long cnt = q.front().second;
		q.pop();
		for (long long i = 0; i < 2; i++) {
			next = nextNum(i, num);
			if (next > B) {
				continue;
			}
			else if (next == B) {
				printf("%lld\n", cnt + 2);
				return 0;
			}
			q.push({ next, cnt + 1 });
		}
	}
	printf("-1\n");
	return 0;
}

DFS 정답코드

#include <iostream>
using namespace std;
#define INF 987654321
long long result = INF;
long long A, B;

void dfs(long long num, long long cnt)
{
	if (num > B) return;
	if (num == B) {
		result = cnt;
		return;
	}
	dfs(num * 2, cnt + 1);
	dfs(num * 10 + 1, cnt + 1);
}
int main()
{
	cin >> A >> B;
	if (A == B) {printf("0\n"); return 0;}
	dfs(A, 0);
	printf("%lld\n", result == INF ? -1 : result + 1);
	return 0;
}