문제

문제링크

n에서 k로 이동해야하는데 2*n,n-1,n+1로 이동했을때 최소횟수를 구하는 문제다.
dp 처럼 보이기도한다.

그래프를 타고 내려갔을때 최소 횟수를 구하면된다.

비슷한 문제를 풀어봤었을때 2n은 횟수를 차감하지않아 2n 먼저 시도했는데
이 문제는 모두 1코스트로 비용이 같다.

최단횟수를 구할때는 bfs로 풀면 트리의 깊이가 최소임을 보장할수있다.

code

/**
 * 백준 1697
 * 그래프
 * x+1,x-1은 1초 2x는 0초
 * 가장 빠른 시간
*/
#include <bits/stdc++.h>
using namespace std;

bool visited[200000]={false};
int n,k;

int main(void){
    cin >>n>>k;

    if(n==k){
        cout<<0<<endl;
        return 0;
    }

    int maxVal=2*k;
    visited[n]=true;

    queue<vector<int>> que;
    que.push({n,0});
    
    while(!que.empty()){
        vector<int> now = que.front();
        que.pop();
        int qN=now[0];
        int qCost=now[1];

        // qN*2
        int next=qN*2;
        if(next>=0 && next<maxVal && !visited[next]){
            if(next==k){
                cout<<qCost+1<<endl;
                break;
            }

            visited[next]=true;
            que.push({next,qCost+1});
        }

        // qN-1
        next=qN-1;
        if(next>=0 && !visited[next]){
            if(next==k){
                cout<<qCost+1<<endl;
                break;
            }

            visited[next]=true;
            que.push({next,qCost+1});
        }

        // qN+1
        next=qN+1;
        if(next>=0 && !visited[next]){
            if(next==k){
                cout<<qCost+1<<endl;
                break;
            }

            visited[next]=true;
            que.push({next,qCost+1});
        }
    }
}