백준
백준 소스코드 [C++] 1463 1로 만들기 1-BFS
Hani_Levenshtein
2020. 10. 5. 10:50
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
백준 소스코드 [C++] 1463 1로 만들기 BFS
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
bool checked[1000001];
int n;
int bfs() {
queue<int> q,r;
q.push(n);
checked[n] = true;
int res = 0;
while (q.empty() != true) {
while (q.empty() != true) {
r.push(q.front());
q.pop();
}
while (r.empty() != true) {
int t = r.front();
r.pop();
if (t == 1) return res;
if (t % 3 == 0 && checked[t / 3] == false) {
checked[t / 3] = true; q.push(t / 3);
}
if (t % 2 == 0 && checked[t / 2] == false) {
checked[t / 2] = true; q.push(t / 2);
}
if (checked[t - 1] == false) {
checked[t - 1] = true; q.push(t - 1);
}
}
res++;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
cout<<bfs();
return 0;
}