[백준/BOJ] 백준 12851번 : 숨바꼭질 2

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

bfs를 통해 start에서 dest로 가는 가장 빠른 시간을 구하는데, 가장 빠른 시간으로 가는 방법의 수도 구해야 되므로, there로 이동할 때 there가 발견된 적이 있어도 depth[here] + 1 == depth[there]이면 이동할 수 있도록 했다.

 

코드

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

int discovered[100001];
int depth[100001];
int num = 0;

void Pre()
{
	for (int i = 0; i < 100001; i++)
		discovered[i] = 0;
}

void Solve(int start, int dest)
{
	Pre();

	discovered[start] = 1;
	depth[start] = 0;

	queue<int> q;
	q.push(start);

	while (!q.empty())
	{
		int here = q.front();
		q.pop();

		//목적지에 도착했을때
		if (here == dest)
		{
			num++; //개수를 센다

			continue; //더 깊은 depth로 탐색하지는 않는다
		}

		for (int i = 0; i < 3; i++)
		{
			int there = here;

			if (i == 0) //앞쪽으로 걷기
				there++;

			else if (i == 1) //뒤쪽으로 걷기
				there--;

			else if (i == 2) //순간이동
				there = there * 2;

			//there가 발견된적이 있어도 depth[here] + 1 == depth[there]이면 이동할 수 있다
			if (there >= 0 && there <= 100000 && (discovered[there] == 0 || depth[here] + 1 == depth[there]))
			{
				discovered[there] = 1;
				depth[there] = depth[here] + 1;

				q.push(there);
			}
		}
	}
}

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

	int n, k;
	cin >> n >> k;

	Solve(n, k);

	cout << depth[k] << "\n";
	cout << num;

	return 0;
}