[백준 알고리즘] 13549번: 숨바꼭질 3
April 04, 2021
https://www.acmicpc.net/problem/13549
문제
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
풀이
간선정보를 직접 만들어서 다익스트라 알고리즘을 적용해야 하는 문제였다. 한 지점에서 갈 수 있는 경우의 수는 +1, -1, X2 가 있기 때문에 이 위치가 유혀한 범위(0 < X < 100001) 라면 우선순위 큐에 넣어준다.
우선순위 큐에 넣을 때는, 기존에 다익스트라에서 사용하던 간선 비용 대신 해당 움직임으로 소요되는 시간을 넣어준다. 따라서 +1, -1 로 이동할 때는 바로 이전 정점의 시간 +1 을 한 시간으로 우선순위 큐에 넣고, 순간이동을 할때는 이전 정점의 시간을 유지한 채로 우선순위 큐에 넣는다.
코드
#include <iostream>
#include <queue>
#include <climits>
using namespace std;
int dist[100001];
int N, K;
struct Compare {
bool operator()(pair<int, int>& a, pair<int, int>& b) {
return a.first > b.first;
}
};
void dijkstra(int start) {
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
pq.push({ 0, start });
while (!pq.empty()) {
int next = pq.top().second;
int costHere = pq.top().first;
pq.pop();
if (next < 100000 && dist[next + 1] > costHere + 1) {
dist[next + 1] = costHere + 1;
pq.push({ costHere + 1, next + 1 });
}
if (next > 0 && dist[next - 1] > costHere + 1) {
dist[next - 1] = costHere + 1;
pq.push({ costHere + 1, next - 1 });
}
if (next < 50001 && dist[next * 2] > costHere) {
dist[next * 2] = costHere;
pq.push({ costHere, next * 2 });
}
}
}
int main() {
cin >> N >> K;
for (int i = 0; i <= 100000; i++) {
dist[i] = INT_MAX;
}
if (N == K) {
cout << "0";
return 0;
}
dijkstra(N);
cout << dist[K];
}
