백준 13549 숨바꼭질3 c++ // pq를 이용한 bfs 구현방법

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

13549번: 숨바꼭질 3

1. 문제

그냥 bfs : 메모리초과? 가 났다.

bfs는 비용이 모두 동일할때만 사용 가능하다.

해결 : 비용이 적은것부터 탐색하도록 pq에 담는다.

 

2. 전체코드

#include <bits/stdc++.h>
using namespace std;

int n, k;
int vis[100000 + 4];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >>k;
	
	//비용, 정점
	priority_queue <pair<int, int>,
					vector<pair<int,int>>,
					greater<>> pq;
	
	//비용이 적은것부터 탐색함
	pq.push({ 0,n});
	while (pq.size()) {
		auto cur = pq.top(); pq.pop();
		//cout << cur.first << " " << cur.second << "\n";

		if (cur.second < 0 || cur.second >= 100000 + 4) continue;
		if (cur.second == k) {
			cout << cur.first;
			return 0;
		}

		if (vis[cur.second]) continue;
		vis[cur.second] = 1;
		pq.push({ cur.first + 1, cur.second + 1 });
		pq.push({ cur.first + 1, cur.second - 1 });
		pq.push({ cur.first, cur.second*2 });
	}

	return 0;
}