백준 13549번 숨바꼭질 3

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

13549번: 숨바꼭질 3

 

 

 

 

<접근방법>

기존의 숨바꼭질과 다르게 순간이동의 가중치가 0입니다.

즉, 큐에 들어가있는 가중치가 정렬되어 있지 않습니다.

이것을 해결하기 위해 우선순위 큐를 이용하였습니다.

 

주의할 점은 큐에서 뺄 때, 방문체크를 하여야 합니다.

그래야 가중치를 정렬된 상태로 이용할 수 있습니다.

 

 

<느낀 점>

 

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct point {
	int x, cnt;
};

int n, k;
bool visit[100001];

struct cmp {
	bool operator()(point a, point b) {
		return a.cnt > b.cnt;
	}
};

priority_queue<point, vector<point>, cmp> q;

void bfs() {
	q.push({n, 0});

	while (!q.empty()) {
		int x = q.top().x;
		int cnt = q.top().cnt;
		int nx;
		q.pop();

		visit[x] = true;

		if (x == k) {
			cout << cnt << '\n';
			return;
		}

		nx = x + 1;
		if (0 <= nx && nx <= 100000 && !visit[nx]) {
			q.push({nx, cnt + 1});
		}

		nx = x - 1;
		if (0 <= nx && nx <= 100000 && !visit[nx]) {
			q.push({ nx, cnt + 1 });
		}

		nx = x * 2;
		if (0 <= nx && nx <= 100000 && !visit[nx]) {
			q.push({ nx, cnt});
		}
	}
}

int main() {
	cin >> n >> k;

	bfs();

	return 0;
}