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

걷거나 순간이동해서 가장 빠르게 동생의 위치를 찾는 방법이 몇 가지인지 찾는 문제이다.

 

이 문제는 가장 빠른 시간 안에 이동하는 문제이기 때문에 BFS를 사용할 수 있다.

이런 식으로 BFS를 통해서 모든 경우의 수를 탐색해 주면 최단시간을 구할 수 있다. 그런데 여기서 정말로 모든 경우의 수를 계산하게 된다면 너무 많은 경우의 수가 존재해서 메모리 초과가 발생한다. 그래서 visited라는 배열을 둬서 이미 방문한 곳은 다시 방문하지 않게 하는 게 이 문제의 핵심이다.

 

만약 시간이 0초이고 시작 지점이 1이라고 생각을 해보자. 동생이 만약 4에 있다면 1 2 4가 가장 빠른 경로이다.

1에서 2로 가는 경우의 수는 2가지가 있다. (걸어서 가거나 순간이동해서 가거나)

위 2가지는 다른 방법이다. 그래서 시간이 같은 경우에는 중복을 허용해야 한다. 0초일 때 1에서 2로 가는 경우의 수가 2개가 있음. 방문을 한 후에 방문처리를 해줘야 함.(시간이 같다면 중복해서 큐에 넣는것도 허용한다.)

 

#include <iostream>
#include <queue>

using namespace std;

queue<pair<int, int>> q;

int visited[100001];

int main(void)
{
	int N = 0;
	int K = 0;

	int time = 0;
	int result = 0;
	int sig = 0;
	cin >> N >> K;

	q.push({ N,0 });

	while (!q.empty())
	{
		int num = q.front().first;
		int count = q.front().second;
		visited[num] = 1;//방문을 한 다음에 방문처리.
		q.pop();

		if (num == K && sig == 0)
		{
			time = count;
			sig = 1;
		}

		if (num == K && sig == 1 && time == count)
		{
			result++;
		}

		if (num - 1 >= 0 && visited[num - 1] == 0)
		{
			q.push({ num - 1,count + 1 });//넣으면서 방문처리를 하지 않는다. 시간이 같다면 중복해서 큐에 넣는것도 허용한다.
		}
		if (num + 1 <= 100000 && visited[num + 1] == 0)
		{
			q.push({ num + 1,count + 1 });
		}
		if (num * 2 <= 100000 && num * 2 >= 0 && visited[num * 2] == 0)
		{
			q.push({ num * 2,count + 1 });
		}

	}

	cout << time << endl;
	cout << result;

	return 0;
}