문제

문제 링크

어떻게 접근할 것인가?

  • n을 큐에 넣고 front 원소를 꺼내서 +1, -1, *2한 후보군을 큐에 다시 넣어준다.
  • 이 때 음수는 못들어가게 해준다.
  • 그 전에 n이랑 k랑 같다면 0을 출력해주는게 함정이다.

코드

#include <cstdio>
#include <queue>

using namespace std;

int arr[500000];
int cand[3];
int n, k, x, c;

int main(){
    queue<int> q;
    scanf("%d %d", &n, &k);
    q.push(n);
    if(n == k) {
        printf("0");
        return 0;
    }
    while(!q.empty()){
        x = q.front(); q.pop();
        c = arr[x];
        cand[0] = x - 1, cand[1] = x + 1, cand[2] = 2 * x;
        for(int i = 0; i < 3; i++){
            int current = cand[i];
            if(current == k){
                printf("%d", c + 1);
                return 0;
            }
            if(current <= 0 || current > 500000)continue;
            if(arr[current] == 0){
                arr[current] = c + 1;
                q.push(current);
            }
            
        }
    }
}

느낀점

  • BFS로 수월하게 패스
  • 함정 조심하시구요 어레이 싸이즈 조심하세요~ㅎㅎ