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

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

12851번: 숨바꼭질 2

백준 12851번 숨바꼭질 2를 풀었다.

 

BFS문제인데 도착하는 경로의 수까지 계산해야 한다.

목적지에 가장 빨리 도착하는 시간을 minTime에 기록해둔다.

목적지에 도착하는 경로에 대해서 시간이 minTime인지 확인한 후 cnt값을 올린다.

BFS 함수가 종료되면 minTime에 동생을 찾는 가장 빠른 시간이 기록되고, cnt에 가장 빠른 시간으로 동생을 찾는 경로의 개수가 기록된다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, k;
int cnt,minTime;
int dx[2] = { -1,1 };
int visited[100001];
queue<pair<int, int>> q; // Location, time

void BFS() {
	while (!q.empty()) {
		int cur = q.front().first;
		int time = q.front().second;
		q.pop();
		visited[cur] = 1;

		if (cnt != 0 && minTime == time && cur == k)
			cnt++;

		if (cnt == 0 && cur == k) {
			minTime = time;
			cnt++;
		}

		for (int i = 0; i < 3; i++) {
			int next;
			if (i == 2)
				next = cur * 2;
			else
				next = cur + dx[i];

			if (next >= 0 && next <= 100000
				&& visited[next] == 0) {
				q.push({ next,time + 1 });
			}
		}
	}
}

int main() {
	cin >> n >> k;
	q.push({ n,0 }); // Start location, time
	BFS();
	cout << minTime << '\n' << cnt;

	return 0;
}