백준 BOJ 13549 - 숨바꼭질 3

다익스트라 연습중

 

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

초(시간) 에 해당하는걸 간선의 가중치로, 각각의 점 위치를 노드로 보면

그래프에서의 N번 노드에서 K번 노드까지의 가중치의 최소값을 구해주면 되므로 다익스트라로

해결할 수 있다.

 

단순한 다익스트라에, 간선조건조차 그리 어려운 편이 아니므로

자세한 설명은 생략해도 괜찮을 것 같다.

 

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

priority_queue<pair<int,int>> pq;

int d[123456] = {0};

void dijkstra(int node){
	for(int i=0; i<123456; i++) d[i] = INF;
	d[node] = 0;
	pq.push({0,node});
	
	while(!pq.empty()){
		int now =  pq.top().second;
		int dir = -pq.top().first;
		pq.pop();
		
		if(0 <= 2*now && 2*now <= 100000){
			if(d[2*now] > dir){
				d[2*now] = dir;
				pq.push({-dir, 2*now});
			}
		}
		
		if(0 <= now+1 && now+1 <= 100000){
			if( d[now+1] > dir + 1 ){
				d[now+1] = dir + 1;
				pq.push({-(dir+1), now+1});
			}
		}
		
		if(0 <= now-1 && now-1 <= 100000){
			if( d[now-1] > dir + 1 ){
				d[now-1] = dir + 1;
				pq.push({-(dir+1), now-1});
			}
		}
	}
	return;
}

int main(){
	int n,k;
	scanf("%d %d", &n, &k);
	
	dijkstra(n);
	
	printf("%d", d[k]);
	return 0;
}