BOJ/백준 13459 숨바꼭질 3

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

13549번: 숨바꼭질 3

언어 : C++17

환경 : VSCode gcc 8.1.0

 

1697번 숨바꼭질과 비슷하다 하지만 여기서는 순간이동을 할 때는 0초 만에 이동하기 때문에

현재 dist의 내용에서 +1을 하지 않고 계속 BFS를 돌려주면 된다. 이때 순간이동이 이동시간이 더 빠르기 때문에

순간이동부터 먼저 계산해준다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int dist[100001];
int main(){
    int n,k;
    queue<int> Q;
    cin >> n >> k;
    fill(dist, dist + 100001, -1);
    dist[n] = 0;
    Q.push(n);
    while(!Q.empty()){
        int cur = Q.front(); Q.pop();
        for(int dir : {cur * 2, cur - 1, cur + 1}){
            if(dir < 0 || dir > 100001) continue;
            if(dist[dir] != -1) continue;
            if(dir == cur * 2) dist[dir] = dist[cur];
            else dist[dir] = dist[cur] + 1;
            Q.push(dir);
        }
    }
    cout << dist[k];
    return 0;
}

결과

 

참고로 덱을 사용해서 풀수도 있다.

 

코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000001
int dist[MAX];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,k;
    deque<int> Dq;
    cin >> n >> k;
    fill(dist, dist + MAX, -1);
    dist[n] = 0;
    Dq.push_front(n);
    while(!Dq.empty()){
        int cur = Dq.front(); Dq.pop_front();
        for(int dir : {cur * 2, cur - 1, cur + 1}){
            if(dir < 0 || dir > MAX) continue;
            if(dist[dir] != -1) continue;
            if(dir == cur * 2){
                dist[dir] = dist[cur];
                Dq.push_front(dir);
            }
            else{
                dist[dir] = dist[cur] + 1;
                Dq.push_back(dir);
            }
        }
    }
    cout << dist[k];
    return 0;
}