[백준 13913] 숨바꼭질 4

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

BFS후에 경로까지 추적하는 문제이다.

BFS할때마다 경로를 저장하면 시간초과가 난다. 따라서 마지막 목적지에 도달했을 때 경로를 역추적해야 한다.

경로 역추적을 위해 부모노드를 저장했다.

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 100000 + 1

using namespace std;

int path[MAX] = {
    0,
};

int parent[MAX] = {
    0,
};

vector<int> answer;

int main(void)
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int s, d;
  cin >> s >> d;
  queue<int> dq;

  dq.push(s);
  path[s] = 1;

  while (!dq.empty())
  {
    int fr = dq.front();

    if (fr == d)
    {
      cout << path[fr] - 1 << "\n";
      int start = fr;
      while (start != s)
      {
        answer.push_back(start);
        start = parent[start];
      }
      answer.push_back(start);

      for (int i = answer.size() - 1; i > -1; i--)
      {
        cout << answer[i] << " ";
      }
      return 0;
    }

    dq.pop();

    if (fr * 2 < MAX && path[fr * 2] == 0)
    {
      path[fr * 2] = path[fr] + 1;
      parent[fr * 2] = fr;
      dq.push(fr * 2);
    }

    if (fr + 1 < MAX && path[fr + 1] == 0)
    {
      path[fr + 1] = path[fr] + 1;
      parent[fr + 1] = fr;
      dq.push(fr + 1);
    }

    if (fr - 1 > -1 && path[fr - 1] == 0)
    {
      path[fr - 1] = path[fr] + 1;
      parent[fr - 1] = fr;
      dq.push(fr - 1);
    }
  }

  return 0;
}