백준 13549 c++ -[PlusUltraCode]

[필자 사고]

이 문제는 최단거리 그래프 탐색 문제이다.

 

다른 문제와 비슷하지만 이 문제의 특이한 점은 2*N을 할 때 소요시간이 0이라는 점이다

 

우리가 알고있는 queue를 사용하자니 나중에 들어오는 2*N은 뒤로 밀려 다른 시간들보다 나중에 
탐색하게 되는 문제가 발생하게 된다.

 

그래서 queue가 아닌 priority_queue를 사용하여 0초로 이동한 값은 자연스레 큐 앞에 배치 되도록 설계했다.

 

[소스코드]

 

 

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

typedef pair<int, int> Node;
priority_queue<Node, vector<Node>, greater<Node>> pq;
vector<int> visited;
int N, M;
int maxSize = 100001;
bool Inside(int num) {
	if (num >= 0 && num < maxSize)return true;
	return false;
}
void BFS() {
	pq.push({ 0, N });
	visited[N] = 0;
	while (!pq.empty()) {
		int nowNum = pq.top().second;
		int nowCount = pq.top().first;
		pq.pop();
		if (nowNum == M) {
			cout << visited[nowNum];
		}
		if (Inside(nowNum*2) && visited[2 * nowNum] == -1) {
			visited[2 * nowNum] = visited[nowNum];
			pq.push({ visited[2 * nowNum],2 * nowNum });
		}
		if (Inside(nowNum-1) && visited[nowNum - 1] == -1) {
			visited[nowNum - 1] = visited[nowNum] + 1;
			pq.push({ visited[nowNum - 1],nowNum - 1 });
		}
		if (Inside(nowNum +1) && visited[nowNum + 1] == -1) {
			visited[nowNum + 1] = visited[nowNum] + 1;
			pq.push({ visited[nowNum + 1],nowNum + 1 });
		}
	}

}

void Input(){
	cin >> N >> M;
	visited.resize(100001, -1);


}

int main(void) {
	Input();
	BFS();
}