[백준] 12851 숨바꼭질 2⭐

[백준] 12851 숨바꼭질 2

• https://www.acmicpc.net/problem/12851

• 주의해야할 테스트 케이스

input: 
0 3
output: 
3
2
//0 -(+1)-> 1 -(+1)-> 2 -(+1)-> 3
//0 -(+1)-> 1 -(*2)-> 2 -(+1)-> 3

#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
#include <algorithm>

using namespace std;

pair<int, int> getMinMove(int start, int end) {
	
	//<-curMove, curX>
	priority_queue<pair<int, int>> q;
	q.push({ 0, start });
	
    //minVisited[x]:
    //x좌표를 방문하지 않은 경우: -1
    //x좌표를 방문한 적이 있는 경우: N에서부터 x까지 이동할 수 있는 최소 시간
	vector<int> minVisited (100001, -1 );
	
    //N에서부터 K까지 이동할 수 있는 최소 시간
	int minMove = -1;
    //minMove 경우의 수
	int cnt = 0;
    
	while (!q.empty()) {
		int curMove = -q.top().first;
		int curX = q.top().second;
		q.pop();

		if ((minMove != -1) && (curMove > minMove)) break;

		if (curX == end) {
			if (minMove == -1) {
				minMove = curMove;
				cnt = 1;
			}
			else if(minMove == curMove){
				cnt++;
			}
			continue;
		}

		if (minVisited[curX] == -1)  
			minVisited[curX] = curMove;
		else if (minVisited[curX] < curMove) 
			continue;

		if (curX - 1 >= 0) {
			if((minVisited[curX-1] == -1) 
				|| ((minVisited[curX - 1] != -1) && (minVisited[curX-1] >= (curMove + 1))))
				q.push({ -(curMove + 1), curX - 1 });
		}

		if (curX + 1 <= 100000) {
			if ((minVisited[curX + 1] == -1) 
				|| ((minVisited[curX + 1] != -1) && (minVisited[curX + 1] >= (curMove + 1))))
				q.push({ -(curMove + 1), curX + 1 });
		}

		if (curX * 2 <= 100000) {
			if ((minVisited[curX*2] == -1) 
				|| ((minVisited[curX* 2] != -1) && (minVisited[curX * 2] >= (curMove + 1))))
				q.push({ -(curMove + 1), curX * 2 });
		}
	}

	return { minMove, cnt };
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, K;
	cin >> N >> K;
	
	pair<int, int> res = getMinMove(N, K);
	cout << res.first << "\n" << res.second;
	return 0;
}

📌참고자료

• [백준] 1697 숨바꼭질
  https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-1697-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88