[BaekJoon] 백준 13549번 숨바꼭질 3

[BaekJoon] 백준 13549번 숨바꼭질 3

 

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

 

 

내코드

 

- 기존의 bfs랑 약간 다른 문제

- 그렇게 쉽지도 어렵지도 않은 문제

- 전에 풀었던 [BaekJoon] 백준 1697번 숨바꼭질 문제와 내용은 비슷하지만 priority queue를 이용해서 순간이동 하는 경우를 따로 처리해줘야하는 점이 달랐다.

- 순간이동하는 경우 시간이 소요되지 않기 때문에 고려해서 priority queue를 사용해주면 된다.

 

#include <iostream>
#include <queue>
#include <utility>

#define MAXNUM 100001

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, k; cin >> n >> k;
	bool visited[MAXNUM] = { false, };
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> qu;
	qu.push(make_pair(0, n));
	visited[n] = true;

	while (!qu.empty()) {
		int sec = qu.top().first;
		int loc = qu.top().second;
		qu.pop();

		if (loc == k) {
			cout << sec;
			return 0;
		}
		if (loc * 2 < MAXNUM && visited[loc * 2] == false) {
			qu.push(make_pair(sec, loc * 2));
			visited[loc * 2] = true;
		}
		if (loc + 1 < MAXNUM && visited[loc + 1] == false) {
			qu.push(make_pair(sec + 1, loc + 1));
			visited[loc + 1] = true;
		}
		if (loc - 1 >= 0 && visited[loc - 1] == false) {
			qu.push(make_pair(sec + 1, loc - 1));
			visited[loc - 1] = true;
		}
	}

	return 0;
}

 

참고