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

12851번: 숨바꼭질 2

cpp

#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. 인접 노드 확인할 때 이미 방문했던 노드도 확인 (모든 경로의 경우를 확인해봐야 하기 때문)