(C++) 백준 13549 숨바꼭질 3

문제 및 풀이

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

bfs로 현재 위치(X)에서 방문 가능한 위치(X+1, X-1, X*2)를 탐색하는 문제
우선순위큐를 써서 문제를 풀면 T=0인 경우들을 먼저 탐색하게 되서 오히려 시간/메모리 적으로 비효율적이었다 ;;
소요되는 시간 T를 기준으로 생각하기 보다 bfs처럼 길이순으로 먼저 방문할 수 있는 곳을 찾는것이 더 맞는거같다

코드

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 200005;
bool isvisited[MAX];
int N,K,ans;

int main(){

    ios_base::sync_with_stdio(0), cin.tie(0);

    cin>>N>>K;

    queue<pair<int, int>> q;
    q.push({N,0});

    while(!q.empty()){

        int tmp = q.front().first;
        int T = q.front().second;
        q.pop();

        if(isvisited[tmp]) continue;
        if(tmp==K) {
            ans = T;
            break;
        }
        isvisited[tmp]=true;

        if(tmp*2<MAX) q.push({tmp*2, T});
        if(tmp-1>=0) q.push({tmp-1, T+1});
        if(tmp+1<MAX) q.push({tmp+1, T+1});

    }

    cout<<ans;

}