[BOJ / C++] #1697 숨바꼭질

https://www.acmicpc.net/problem/13549

문제풀이

#1697 숨바꼭질과 유사한 문제이다.
다만 순간이동을 하는 경우는 0초후가 되는데,
3가지를 모두 큐에 push하는 과정에서, time이 같은 것들이 동시에 들어가야 pop을 했을 때 time이 적은 순서대로 나오기 때문에

deque를 이용해서
time+1로 push되는 일반이동은 deque.push_back을 해주고,

time이 그대로 push되는 순간이동은 deque.push_front로 앞에 push해주는 것이 포인트 ✨

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 100000
bool visited[MAX+1];
int N,K;

int bfs(int time, int pos){

    deque<pair<int,int>> dq;
    visited[pos]=true;
    dq.push_back({time,pos});

    while(!dq.empty()){
        int curTime=dq.front().first;
        int curPos=dq.front().second;

        dq.pop_front();

        if(curPos==K) return curTime;

        //2*x
        if(2*curPos<=MAX&&!visited[2*curPos]){
            visited[2*curPos]= true;
            dq.push_front({curTime,2*curPos}); // 이동거리 (time)이 0이므로 front에 넣어줘야함@@
        }

        //x-1
        if(curPos>=1&&!visited[curPos-1]){
            visited[curPos-1]=true;
            dq.push_back({curTime+1,curPos-1});
        }

        //x+1
        if(curPos<=MAX-1&&!visited[curPos+1]){
            visited[curPos+1]= true;
            dq.push_back({curTime+1,curPos+1});
        }

    }

}

int main(){
    cin>>N>>K;
    cout<<bfs(0, N)<<"\n";
    return 0;
}

c++에서 deque는 처음 써본다 역시 편해~!!~
참고 : https://velog.io/@choiiis/C-STL-deque%ED%81%B4%EB%9E%98%EC%8A%A4-%EC%A0%95%EB%A6%AC