BOJ 13549번: 숨바꼭질 3

문제

문제 바로가기> BOJ 13549번: 숨바꼭질 3

13549번: 숨바꼭질 3

 

풀이

순간이동을 하는데는 시간이 소요되지 않으므로, 해당 위치에 최단 거리로 도착할 수 있도록, 시간을 업데이트해 줄 필요가 있다!

 

#include<iostream>
#include<queue>
#define MAX 100001
using namespace std;

int N, K;
int visit_time[MAX];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> K;
    
    int ans = MAX;// 수빈이가 동생을 찾을 수 있는 가장 빠른 시간
    for(int i=0; i<MAX; i++) visit_time[i] = MAX; // 초기화
    
    queue<pair<int, int>> q;
    visit_time[N] = 0;
    q.push({N, 0});

    while(!q.empty()){
        int pos = q.front().first;
        int sec = q.front().second;
        q.pop();

        if(pos == K) ans = min(ans, sec);
        else{
            if(pos*2 < MAX && visit_time[pos*2] > sec){
                visit_time[pos*2] = sec;
                q.push({pos*2, sec});
            }
            
            if(pos+1 <= K && visit_time[pos+1] > sec+1){
                visit_time[pos+1] = sec+1;
                q.push({pos+1, sec+1});
            }

            if(pos-1 >= 0 && visit_time[pos-1] > sec+1){
                visit_time[pos-1] = sec+1;
                q.push({pos-1, sec+1});
            }
        }
    }
    cout << ans;
}