[백준 12851번 C++] 숨바꼭질 2

기존 문제인 숨바꼭질 문제와 유사하지만, 최단 시간에 도착한 경로의 개수를 찾아야된다는 점에서 차이가 있다.

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

12851번: 숨바꼭질 2

 

따라서 해당 노드와 탐색 깊이를 모두 저장할 수 있는 pair 자료형 queue를 선언해 while loop를 실행한다.

최단 시간을 찾은 이후에도 계속해서 최단시간을 만족하는 경로를 추가해야하기때문에, Queue에 들어온 도착 노드가 최단 시간을 만족하는 경우 더해야한다.

 

해당 코드의 흐름을 정리해보자면 다음과 같다. 

1. 가장 처음 시작하는 노드를 큐에 삽입한다.
   (이때 해당 노드는 아직 다른 노드를 탐색하지 않았기 때문에 depth가 0이다)
2. 이동 가능한 vertex를 큐에 삽입한다. 
     (단 visited[node]가 false 여야 하며, 다음 노드를 탐색하는 것이기 때문에 depth에 1을 더한다)
3. 최단 시간에 도착한 첫번째 경우,  해당 시간대를 저장한다.
4. 이후 최단 시간으로 도착하는 경우, 경우의 수만 카운트한다. 

 

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>

using namespace std;
deque<pair<int, int>> Q;
const int MAX = 100001;
int depth, route;
bool visited[MAX];
vector<int>answer;

void BFS(int s,int e) {
	
	Q.push_back({ s,0 });

	while (!Q.empty()) {

		int cur = Q.front().first;
		int dep = Q.front().second;

		Q.pop_front();

		visited[cur] = true;

		if (depth && depth == dep && cur == e) {
			route++;
		}
		if (!depth &&cur == e) {
			route++;
			depth = dep;
		}

		if (cur + 1 < MAX && !visited[cur+1]){
			Q.push_back({ cur + 1,dep+1 });
		}
		if (cur - 1 >= 0 && !visited[cur - 1]) {
			Q.push_back({ cur - 1,dep + 1 });
		}
		if (cur * 2 < MAX && !visited[cur*2]) {
			Q.push_back({ cur * 2, dep+1 }); 
		}
	}

}

int main() {
	int S, E;
	cin >> S >> E;

	BFS(S, E);

	cout << depth << endl;
	cout << route << endl;

}