알고리즘 연습/백준
[C++][BOJ16953,A → B] DFS,BFS,그리디
_h.j
2021. 7. 20. 11:33
728x90
처음에 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
728x90