문제링크: https://www.acmicpc.net/problem/16953

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다.

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

풀이

#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;

long long A;
long long B;
int ans = INT_MAX;

void bfs(const long long& a, int count) {
	if (a > B) {
		// cout << a << "\n";
		return;
	}
	else if (a == B) {
		ans = min(ans, count);
		// cout << ans << "\n";
	}
	
	bfs(a * 2, count + 1);
	bfs(a * 10 + 1, count + 1);
}

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

	cin >> A >> B;

	bfs(A, 1);

	if (ans == INT_MAX) {
		cout << -1 << "\n";
	}
	else {
		cout << ans << "\n";
	}

	return 0;
}

ans의 값을 int의 최댓값으로 만들어버린다.
그래서 bfs함수 안의 a와 목표값인 B가 같아지면 count를 ans로 업데이트 한다.
그렇게 연산을 비교해 최소의 ans를 찾아낸다.

노트

간단한 bfs의 문제지만 ans라는 변수를 최댓값으로 설정해 min연산을 해야한다는 생각을 미처 하지 못했다.
parameter를 하나 추가하고 많은 방법들을 고민하다 결국 변수 하나를 더 선언해주니 풀렸다.
그래프 탐색은 단순히 그래프를 연결해 방문하는 것만은 아니라고 생각된다.
더 많은 고민이 필요한 문제같다.