백준 13913번 숨바꼭질 4 ( C++ )

문제

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

 

해설

최단경로를 찾는 문제이기 때문에 BFS사용

어떤 경로로 이동했는지를 알려줘야 하기 때문에 last사용(prev로 바꿀것)

 

코드

#include <bits/stdc++.h>
using namespace std;
 
int n, k;
int visited[2000004];
int last[200004];
stack<int> ret;
 
void bfs(int start)
{
  visited[start] = 1;
  queue<int> q;
  q.push(start);
  int now;
  while (q.size())
  {
    now = q.front();
    q.pop();
 
    for (int next : {now + 1, now - 1, now * 2})
    {
      if (next >= 0 && next <= 200000)
      {
        if (!visited[next])
        {
          q.push(next);
          visited[next] = visited[now] + 1;
          last[next] = now;
        }
      }
    }
  }
}
 
int main()
{
  cin >> n >> k;
  if (n == k)
  {
    cout << 0 << "\n";
    cout << k;
    return 0;
  }
 
  bfs(n);
  int check = k;
  while (check != n)
  {
    ret.push(check);
    check = last[check];
  }
  ret.push(n);
 
  cout << visited[k] - 1 << "\n";
  for (int i = 0; i < visited[k]; i++)
  {
    cout << ret.top() << " ";
    ret.pop();
  }
}