공부흔적

문제 링크

풀이 ) 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);
}

주의점 )

  사용여부를 확인하기 전에 해당 인덱스(층)에 방문할 수 있는지, 즉 해당 층이 범위 내에 있는지 확인해야 런타임 에러를 방지할 수 있다.