반응형
풀이 ) BFS
큐에 처음 층을 넣고 큐에서 큐에서 뺄 때 뺀 층에서 갈 수 있는 층을 큐에 넣는다.
이때 목표층에 도착하는 경우 중첩 반복문에서 빠져나오기 위해 바깥쪽 while문에서도 조건에 따른 break를 추가한다.
#include <cstdio>
#include <queue>
using namespace std;
int main(void){
int n, k, ans = 0, used[100001] = {0, };
queue<int> q;
scanf("%d%d", &n, &k);
q.push(n);
q.push(-1);
used[n]++;
while(1){
int tmp = q.front();
while(tmp != -1){
if(tmp == k)
break;
q.pop();
if(tmp>0 && !used[tmp-1]){
used[tmp-1]++;
q.push(tmp-1);
}
if(tmp<99999 && !used[tmp+1]){
used[tmp+1];
q.push(tmp+1);
}
if(tmp<=50000 && !used[tmp*2]){
used[tmp*2];
q.push(tmp*2);
}
tmp = q.front();
}
if(tmp == k)
break;
q.pop();
ans++;
q.push(-1);
}
printf("%d\n", ans);
}
주의점 )
사용여부를 확인하기 전에 해당 인덱스(층)에 방문할 수 있는지, 즉 해당 층이 범위 내에 있는지 확인해야 런타임 에러를 방지할 수 있다.
반응형
'문제풀이 > 백준' 카테고리의 다른 글
[C++] 백준 - 3085 : 사탕 게임 (0) | 2020.11.06 |
---|---|
[C++] 백준 - 2231 : 분해합 (0) | 2020.11.06 |
[C++] 백준 - 13458 : 시험 감독 (0) | 2020.04.30 |
[C++] 백준 - 17070 : 파이프 옮기기 1 (0) | 2020.04.15 |
[C++] 백준 - 5014 : 스타트링크 (0) | 2020.04.05 |