숨바꼭질3

코드

#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

int dx[3] = {2, -1, 1};
int board[200001];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, K;
    cin >> N >> K;
    queue<int> q;
    q.push(N);
    board[N] = 1;
    if(N == K){
        cout << 0;
        return 0;
    }
    while(!q.empty())
    {
        int cur = q.front(); q.pop();
        for(int i=0;i<3;i++)
        {
            int nx;
            if(i != 0) nx = cur + dx[i];
            else nx = cur*dx[i];
            if(nx < 0 || nx >= 200000 || board[nx] ) continue;
            q.push(nx);
            if(i != 0) board[nx] = board[cur] + 1;
            else board[nx] = board[cur];

            if(nx == K){
                cout << board[nx] - 1 ;
                return 0;
            }
        }
    }
    return 0;
}

• key point!
  : 현재 값의 2배로 이동하는 cost가 0이기 때문에 가중치가 제일 높아야한다. --> 가장 먼저 이동하게 dx[] 조정!
  (관련 반례 : 0,2 --> 1이 나와야 함!)