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

문제

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

 

해설

최단거리를 묻는 문제이기 때문에 BFS사용

모든 경우의 수를 구하라고 했기 때문에 visited 이외에 cnt를 사용하여 경우의 수 계산

 

코드

#include <bits/stdc++.h>
using namespace std;
 
int n, k;
int visited[200001];
int cnt[200001];
 
void bfs(int num)
{
  queue<int> q;
  int now_num = num;
  q.push(num);
  visited[num] = 1;
  cnt[num] = 1;
  while (q.size())
  {
    now_num = q.front();
    q.pop();
    for (int next_num : {now_num + 1, now_num - 1, now_num * 2})
    {
      if (next_num >= 0 && next_num <= 200000)
      {
        if (!visited[next_num])
        {
          q.push(next_num);
          visited[next_num] = visited[now_num] + 1;
          cnt[next_num] = cnt[now_num];
        }
        else if (visited[next_num] == visited[now_num] + 1)
        {
          cnt[next_num] += cnt[now_num];
        }
      }
    }
  }
}
 
int main()
{
  cin >> n >> k;
  if (n == k)
  {
    cout << 0 << "\n";
    cout << 1;
    return 0;
  }
  bfs(n);
 
  cout << visited[k] - 1 << "\n";
  cout << cnt[k];
}