#include<iostream>
#include<queue>
#include <algorithm>
using namespace std;
int main() {
int num;
cin >> num;
queue<int> q;
q.push(num);
int cnt = 0;
int tmp;
bool visited[1000001] = { false, }; //탐색했던 숫자를 재 탐색하지 않도록 하게 해주는 확인 배열
while (1) {
int qs = q.size(); //레벨 별 숫자들의 갯수 큐값 측정을 통한 qs로 책정
cnt++;
for (int i = 0; i < qs; i++) {
tmp = q.front();
q.pop();
if (!visited[tmp/3] && tmp % 3 == 0) { //탐색했던 숫자 인지 확인
if (tmp / 3 == 1) {
cout << cnt; //카운트 수 출력 바로 프로그램 종료
return 0;
}
else {
q.push(tmp / 3);
}
}
if (!visited[tmp/2] && tmp % 2 == 0) {
if (tmp / 2 == 1) {
cout << cnt;
return 0;
}
else {
q.push(tmp / 2);
}
}
if (!visited[tmp - 1]) {
if (tmp - 1 == 1) {
cout << cnt;
return 0;
}
else
q.push(tmp - 1);
}
visited[tmp] = true;
}
}
}
다른 분이 작성한거 퍼온 코드인데요!
한 값에 대해서
/3
/2
-1
한 값을 큐에 넣고 큐가 빌때까지 반복하는데
큐에 들어가는 개수가 while이 한번 돌때마다 *3개씩 증가하지않습니까?
1->3->9->18 이렇게 되는데
1일때는 레벨0, 3일때는 레벨1, 9일때는 레벨2, 18일때는 레벨3 이라고 한다면.
저 안의 cnt++;는 큐에서 remove할때마다 올라가는거니 cout << cnt를 해버리면
remove된 총 횟수가 cnt가 되는거지 레벨이 되는게 아니지 않나요?
qs라는걸 왜 잡는지 이해를 해보려고 하는게 좋을거 같음. cnt는 거리를 말하는게 맞고.. 처음 점에서 거리 1인 애들을 큐에 다 넣는다 -> cnt를 1로 만들고 거리 1인 애들을 빼면서 거리 2인 애들을 큐에 넣는다 -> cnt를 2로 만들고 거리2인 애들을 빼면서 거리 3인 애들을 큐에 넣는다. 이러면서 1 나오면 바로 출력해버림
나 같은 경우에는 visited 배열을 int로 잡고 그 배열에 현재 점의 거리를 기록하는 방식을 더 선호함.
감사합니다 qs가 어떤 용도로 쓰는지 이해했습니다!