백준 16953 A->B

www.acmicpc.net/problem/16953

16953번: A → B

A, B 범위가 10^9길래 visited 배열은 두지 않고 (이때부터 실패를 예감함..) bfs 구현했는데, 역시 틀렸다.

순서를 반대로 생각하니 풀렸다. A를 B로 만드는 것이 아니라, B를 A로 만들 수 있는지 확인하는 것.

 

ex) a=2, b=162라면 162는 2로 나눠질 뿐 뒤에서 1을 뺄 수는 없으므로 2로 나누면 81, 1을 빼면 8, 2로 나누면 4, 2

 

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

void bfs(int a, int b) {
	queue<pair<int, int>> q;

	q.push({ b, 1 });
	while (!q.empty()) {
		int cur = q.front().first;
		int n = q.front().second;
		q.pop();
		//2로 나눠지면 나누기
		if (cur % 2 == 0) {
			if (cur / 2 == a) {
				cout << n + 1;
				return;
			}
			else if (cur / 2 > a)
				q.push({ cur / 2, n + 1 });
		}
        //1의자리가 1이면 떼어내기
		if (cur % 10 == 1) {
			if (cur / 10 == a) {
				cout << n + 1;
				return;
			}
			else if (cur / 10 > a)
				q.push({ cur / 10, n + 1 });
		}
	}
	cout << -1;
}

int main() {
	int a, b;
	cin >> a >> b;
	bfs(a, b);
}