[BAEKJOON] 13549번 숨바꼭질3

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

13549번: 숨바꼭질 3

 

문제조건

1. 수빈이와 동생이 있다. 
2. 걷는다 : X+1 or X-1 (1초)
3. 순간이동 : 2 * X (0초) ☞ 시간 안걸림
4. 수빈이가 동생을 찾는 가장 빠른시간?

문제를 보고 수빈이와 동생이 아닌, 출발지와 목적지로 생각을 바꿔봤다.

그러면 문제가 평소에 익숙하게 보던 최단거리 찾기가 된다.

 

그러나, 일반적인 최단거리 찾기와 다른 점은 순간이동을 할때는 시간이 안걸린다는 점이다.

이러면 가중치가 서로 달라서 평소에 하던대로 BFS로 최단거리를 구하면 안된다.

 

우선순위 큐(Priority Queue)  를 사용한다면, 쉽게 풀수 있다. 순간이동이 우선순위가 되면  최단시간으로 구할 수 있게된다.

#include <iostream>
#include <queue>
#define MAX 100001
using namespace std;

int n, k, visited[MAX];
// 1. 걷기 : x-1 or x+1 (1초뒤)
// 2. 순간이동 : 2*x (0초뒤) --> 시간 안걸림

int bfs(int s, int e) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({0, s});
	visited[s] = 1;
	while (!pq.empty()) {
		int time = pq.top().first;
		int x = pq.top().second;
		pq.pop();

		if (x == e) return time;
		if (2 * x < MAX && !visited[x * 2]) {
			pq.push({ time,x * 2 });
			visited[2 * x] = 1;
		}
		if (x + 1 < MAX && !visited[x + 1]) {
			pq.push({ time + 1,x + 1 });
			visited[x + 1] = 1;
		}
		if (x - 1 >= 0 && !visited[x - 1]) {
			pq.push({ time + 1,x - 1 });
			visited[x - 1] = 1;
		}
	}
}

int main(){
	cin >> n >> k;
	cout << bfs(n, k);
}

 

여기서 priority_queue는 #include <queue>파일에 포함되어 있다. 그리고 그냥 선언 해주게 된다면, 값이 가장 높은 게 top에 오게 되는 최대힙으로 되므로, 이 문제에서는 시간을 기준으로 오름차순 우선순위를 주기위해서 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; 로 top에 시간이 가장 작은 것이 우선순위를 갖도록 선언해주었다.