[백준 / BOJ] C++ 13913 숨바꼭질 4

13913번: 숨바꼭질 4

 

문제

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

13913번: 숨바꼭질 4

 

 

풀이

1697번 숨바꼭질 문제의 확장된 버전이다. 최단 시간뿐 아니라 그 경로도 구하는 문제다.

[1697 숨바꼭질 문제] | [1697 숨바꼭질 풀이]

 

x+1, x-1, x*2를 탐색할 때 한 번 방문한 점은 다시 방문하지 않으므로 어느 점에 방문할 때 어느 점에서 이동했는지를 기록하는 bef 배열을 만들었다. 존재할 수 없는 -1로 초기화를 하고 BFS가 종료된 후 K 위치부터 역으로 찾아가며 N이 될 때까지 배열에 추가해 준다. 이 배열을 역순으로 출력하면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> visited(100001, 0), bef(100001, -1);

void bfs(int start) {
  queue<int> q;
  q.push(start);
  while (!q.empty()) {
    int x = q.front();
    if (x == k)
      break;
    q.pop();
    if (x + 1 >= 0 && x + 1 <= 100000)
      if (!visited[x + 1]) {
        q.push(x + 1);
        visited[x + 1] = visited[x] + 1;
        bef[x + 1] = x;
      }
    if (x - 1 >= 0 && x - 1 <= 100000)
      if (!visited[x - 1]) {
        q.push(x - 1);
        visited[x - 1] = visited[x] + 1;
        bef[x - 1] = x;
      }
    if (x * 2 >= 0 && x * 2 <= 100000)
      if (!visited[x * 2]) {
        q.push(x * 2);
        visited[x * 2] = visited[x] + 1;
        bef[x * 2] = x;
      }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> k;
  bfs(n);
  cout << visited[k] << '\n';
  int tmp = k;
  vector<int> ans;
  while (tmp != n) {
    ans.push_back(tmp);
    tmp = bef[tmp];
  }
  ans.push_back(tmp);
  for (int i = ans.size() - 1; i >= 0; i--)
    cout << ans[i] << ' ';
  cout << '\n';
  return 0;
}