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

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

13549번: 숨바꼭질 3

백준 13549번 숨바꼭질 3을 풀었다.

 

처음엔 BFS를 사용해서 풀었다가 틀렸다. 간선의 가중치가 다른 경우엔 BFS를 함부로 사용하면 안된다는 것을 알았다. 우선순위 큐를 사용하지 않으면 dist배열 값에 더 큰 비용이 덮어씌어지는 것 같다.

그래서 다익스트라 알고리즘으로 문제를 해결했다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define INF 100001

struct compare {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		return a.second > b.second;
	}
};

int n, k;
vector<int> dist;
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;

void Dijkstra() {
	while (!pq.empty()) {
		int cur = pq.top().first;
		int cost = pq.top().second;
		pq.pop();
		for (int i = 0; i < 3; i++) {
			int next, next_cost;
			if (i == 0) {
				next = cur - 1;
				next_cost = cost + 1;
			}
			if (i == 1) {
				next = cur + 1;
				next_cost = cost + 1;
			}
			if (i == 2) {
				next = cur * 2;
				next_cost = cost;
			}

			if (next >= 0 && next <= 100000) {
				if (dist[next] > next_cost) {
					dist[next] = next_cost;
					pq.push({ next,next_cost });
				}
			}
		}
	}
}

int main() {
	cin >> n >> k;
	dist.assign(100001, INF);

	dist[n] = 0;
	pq.push({ n,dist[n] });

	Dijkstra();

	cout << dist[k];

	return 0;
}