[백준] 13913 숨바꼭질4 - javascript

📌 문제

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

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let [n, k] = input[0].split(" ").map(Number);
let visited = new Array(100001).fill(0);
let path = new Array(100001).fill(0);
function BFS() {
  let L = 0;
  let queue = [];
  queue.push(n);
  visited[n] = 1;
  while (queue.length) {
    let len = queue.length;
    for (let i = 0; i < len; i++) {
      let x = queue.shift();
      if (x === k) {
        return L;
      }
      for (let nx of [x + 1, x - 1, x * 2]) {
        if (visited[nx] === 0 && nx >= 0 && nx <= 100000) {
          path[nx] = x;
          visited[nx] = 1;
          queue.push(nx);
        }
      }
    }
    L++;
  }
}
let time = BFS();
let ans = [];
let before = path[k];
ans.push(k);
for (let i = 0; i < time; i++) {
  ans.push(before);
  before = path[before];
}
console.log(`${time}\n${ans.reverse().join(" ")}`);

✔ 알고리즘 : BFS

✔ 기존의 숨바꼭질 문제에서 경로만 추가하여 출력해주면 되는 문제이다.

✔ 경로를 추적하기 위해 path 배열을 생성하였고 x위치에서 파생되는 nx로 이동가능 하다면 path[nx]에 x를 넣어주어 경로역추적이 가능하게끔 구현하였다.

✔ BFS 함수의 return 값으로 동생을 찾는 가장 빠른 시간을 저장한다.

✔ ans배열에 가장 빠른 시간으로 갈 수 있는경로를 저장하였다.

✔ 동생이 있는 지점부터 path배열을 통해 직전에서 어디서 왔는지 ans배열에 저장해준다

✔ 역추적한 경로이므로 reverse함수를 사용하여 뒤집은 후 join으로 띄어쓰기하여 출력해주었다

✔ 난이도 : 백준 기준 골드4