백준 16953 c++ "A -> B" -[PlusUltraCode]

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

16953번: A → B

 

[필자 사고]

 

단순 탐색문제이다.

 

필자는 단순탐색 보다는 우선순위를 이용하여 문제를 해결했다.

 

 A의 값에 2를 곱한값이 B보다 작을경우 넣고

 

A의 값에 10을 곱하고 +1한값이  B보다 작을경우 넣는 형식으로 코드를 완성했다.

 

주의할 점은 범위가 10^9이므로 long or long long 을 써줘야 된다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;

long long A, B;

void Input() {
	cin >> A >> B;

}

typedef struct Node {
	long long number;
	long long count;
}Node;

struct cmp {
	bool operator()(Node a, Node b) {
		return a.count > b.count;
	}
};

void BFS() {
	priority_queue<Node, vector<Node>, cmp> pq;
	pq.push({ A,0 });
	while (!pq.empty()) {
		long long nowNumber = pq.top().number;
		long long acCount = pq.top().count;
		if (nowNumber == B) {
			cout << acCount + 1;
			return;
		}
		pq.pop();
		long long nextNumber = nowNumber * 2;
		if (nextNumber <= B) {
			pq.push({ nextNumber,acCount + 1 });
		}

		nextNumber = nowNumber * 10 + 1;
		if (nextNumber <= B) {
			pq.push({ nextNumber,acCount + 1 });
		}
	}

	
	cout << -1;
}

int main(void) {
	Input();
	BFS();
}