[백준 C++] 12851 숨바꼭질 2 - 너비우선탐색

12851번: 숨바꼭질 2

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

int Time[100001];
int Count[100001];
bool Visited[100001];
queue<int> SQ;

void NeighborCheck(int Neighbor, int Current)
{
	if (Neighbor < 0 || Neighbor > 100000)
	{
		return;
	}

	int CurTime = Time[Neighbor];
	int NewTime = Time[Current] + 1;
	if (NewTime < CurTime)
	{
		Time[Neighbor] = NewTime;
		Count[Neighbor] = Count[Current];
	}
	else if (NewTime == CurTime)
	{
		Count[Neighbor] += Count[Current];
	}

	SQ.emplace(Neighbor);
}

void BFS(int Start, int End)
{
	Time[Start] = 0;
	Count[Start] = 1;
	SQ.emplace(Start);
	while (!SQ.empty())
	{
		int Current = SQ.front();
		SQ.pop();

		if (Visited[Current])
		{
			continue;
		}

		Visited[Current] = true;
		NeighborCheck(Current - 1, Current);
		NeighborCheck(Current + 1, Current);
		NeighborCheck(2 * Current, Current);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	for (int i = 0; i <= 100000; ++i)
	{
		Time[i] = 1000000;
	}

	int N, K;
	cin >> N >> K;

	if (N != K)
	{
		BFS(N, K);
	}
	else
	{
		Time[K] = 0;
		Count[K] = 1;
	}

	cout << Time[K] << '\n';
	cout << Count[K];
}

---

 

일반적인 BFS 문제들보다 조건이 까다로운 문제입니다.

문제 풀이 시 중요한 부분은 다음과 같습니다.

 

1. 각 노드로 향하는 최단경로의 개수를 저장하는 Count 배열 관리

1-a. 해당 노드에 도착했을 때, 최단경로가 갱신되면 이전 노드의 Count 개수를 전달 받는다.

1-b. 해당 노드에 도착했을 때, 최단경로와 같은 길이로 도착했다면 이미 저장된 Count 값에 이전 노드의 Count 개수를 더해준다.

2. 인접 노드 확인할 때 이미 방문했던 노드도 확인 (모든 경로의 경우를 확인해봐야 하기 때문)