[BOJ 13549] 숨바꼭질 3

🔗Link

문제
풀이

💡Idea

최단 거리(시간)를 구하는 것이기 때문에 bfs로 풀면 된다.
주의할 점은 순간 이동을 할 때는 0초가 걸린다는 점이다.
가장 빠른 시간을 구하는 것이기 때문에, 순간 이동을 하는 경우를 우선 순위를 높게 두어서 풀어야 한다.

🔑Code

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int N, K;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
int vis[100'001];

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> K;

    vis[N] = 1;
    pq.emplace(vis[N],N);
    while(!pq.empty()){
        int cur = pq.top().Y; pq.pop();
        // cout << cur << "(" << vis[cur] << ")" << " -> ";

        if(cur == K) {
            cout << vis[cur] - 1;
            break;
        }

        for(int nxt: {cur * 2, cur - 1, cur + 1}){
            if(nxt < 0 || nxt > 100'000 || vis[nxt] != 0) continue;
            if(nxt == cur * 2){
                // 거리가 더 멀어지면 조기 종료.
                int cur_distance = abs(K - cur);
                int nxt_distance = abs(K - nxt);
                if(nxt_distance >= cur_distance) continue;

                vis[nxt] = vis[cur];
                pq.emplace(vis[nxt], nxt);
            } else{
                vis[nxt] = vis[cur]+1;
                pq.emplace(vis[nxt], nxt);
            }
        }
    }

    return 0;
}

🗨️ Side Notes

주로 이차원 공간에서의 이동을 구현할 때 다음과 같이 구현한다.

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

for(int i = 0; i < 4; i++){
	int nx = x + dx[i];
	int ny = y + dy[i];
	/* 생략 */
}

여러 복합적인 이동이 필요할 때는 범위 기반for 문을 사용하면 편리하다.

for(int nxt: {cur * 2, cur - 1, cur + 1}){
	/* 생략 */
}