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

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

13549번: 숨바꼭질 3

---

접근 방식

0초의 시간을 사용하는 순간이동이 있기때문에, BFS보다 다익스트라가 적합한 문제이다.

출발점에서 부터 +1,-1,*2씩 해서 큐에 넣어주는데, *2를 하는 순간이동은 시간이 걸리지 않기 때문에 순간이동부터 연산을 진행시켜주면 된다.

시간 순서적으로 방문하기 때문에 이미 방문한 지점은 더 탐색할 필요가 없다.

---

코드

#include<iostream>
#include<queue>
#include<cmath>
#include<string>
#include<stack>
#include<vector>
#include<cmath>
#include<tuple>
using namespace std;
int n, m;
int arriveTime[100001];
bool flag[100001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	priority_queue<pair<int, int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;//작은 순서대로
	pq.push({ 0,n });	
	while (!pq.empty()) {
		int curPosition = pq.top().second;
		int curTime = pq.top().first;
		pq.pop();
		if (flag[curPosition])continue;
		flag[curPosition] = true;
		arriveTime[curPosition] = curTime;
		if (curPosition == m) {
			cout << curTime;
			return 0;
		}
		if(curPosition+1<=100000)
		pq.push({  curTime + 1 ,curPosition + 1 });
		if(curPosition-1>=0)
		pq.push({  curTime + 1,curPosition - 1 });
		if(curPosition*2<=100000)
		pq.push({  curTime ,curPosition * 2});
	}

}

---