[백준/C++] 13549번 숨바꼭질 3

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

13549번: 숨바꼭질 3

 

문제 분석

수빈이가 동생을 찾는 가장 빠른 시간을 구하는 문제다. 수빈이는 1초에 한 칸씩 앞뒤로 걷거나, 0초에 현재 위치*2의 위치로 순간이동이 가능하다. 다익스트라 알고리즘을 사용하여 풀 수 있다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define INF 987654321

int n, k;
vector<pair<int, int>> vec[100010];
priority_queue<pair<int, int>> pq;
int dist[100010];

void dijk(int start){
	dist[start] = 0;
	pq.push({0, start});
	while(!pq.empty()){
		int cur = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		if(dist[cur]<cost) continue;
		for(int i=0; i<vec[cur].size(); i++){
			int next = vec[cur][i].second;
			int ncost = vec[cur][i].first;
			if(dist[next]> cost+ncost){
				dist[next] = cost+ncost;
				pq.push({-dist[next], next});
			}
		}
	}
}

int main(){
	cin>>n>>k;
	
	for(int i=0; i<=100000; i++){
		if(i-1>=0) vec[i].push_back({1, i-1});
		if(i+1<=100000) vec[i].push_back({1, i+1});
		if(i*2<=100000) vec[i].push_back({0, i*2});
	}
	
	for(int i=0; i<100010; i++){
		dist[i] = INF;
	}
	
	dijk(n);
	
	cout<<dist[k];
	
	return 0;
}

 

문제 풀이

1. 수빈이의 위치 n과 동생의 위치 k를 입력받는다.
2. 인덱스 i 벡터에 i +-1의 위치까지 가는데 걸리는 시간 1과 i+-1, i *2의 위치까지 가는데 걸리는 시간 0과 i*2를 pair로 붂어서 push한다.
3. 거리를 저장할 dist배열을 INF값을 초기화해준다.
4. 수빈이는 n에서 출발하므로 n을 인자로 dijk함수를 호출한다.(다익스트라)
5. dijk함수에서는 dist 출발지 값을 0으로 두고 0과 출발지를 pair로 묶어서 우선순위 큐 pq에 push한다.
6. 그 후 while문을 통하여 다익스트라 알고리즘을 통해 dist배열을 채운다. cur는 현재 위치고 cost는 cur까지 가기 위해 걸리는 시간이다. 우선순위 큐는 내림차순으로 정렬되므로 시간이 적게 걸리는 것이 앞으로 오도록 -를 붙여서 cost값으로 설정한다. 그 후 for문으로 다음 위치까지 가는데 걸리는 최소 시간을 구해준다.
7. dijk함수가 끝나면 dist배열에 각 위치로 가는데 걸리는 최소 시간이 저장되어 있으므로 dist[k]를 출력한다.