[C++][BOJ16953,A → B] DFS,BFS,그리디

A → B 문제

 

처음에 DFS로 하려고 했으나

출력하는 level의 문제가 있었기 때문에

BFS로 바꿨다. que에 pair로 숫자와 level을 함께 넣어 풀었다.

풀때 타입 주의

 

 

소스 코드

//#include <iostream>
//#include <queue>
//#include <utility>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
ll input_num,target_num,result=0;

//
//void DFS(int current_num, int depth){
//	if(current_num == target_num){
//		cout<<depth;
//		return;
//	}
//	
//	if(current_num*2 <=target_num) DFS(current_num*2,depth+1);
//	if(current_num*10+1 <=target_num) DFS(current_num*10+1,depth+1);
//}

void BFS(){
	queue<pli> q;
	q.push({input_num,1} );

	while(!q.empty()){
		ll current_num = q.front().first;
		int current_depth = q.front().second;
		
		if(current_num == target_num){
			cout<<current_depth;
			return;
		}
			
		if(current_num*2 <= target_num) q.push({current_num *2,current_depth+1});
		if(current_num*10 + 1 <= target_num) q.push({current_num*10 + 1,current_depth+1});
		q.pop();
	}
	
	
	cout<<"-1";
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> input_num>>target_num;
	//DFS(input_num,1);
	BFS();
	
}

 

다른 방법으로 푼 풀이도 있다

https://www.acmicpc.net/source/17668154