[백준] 13549 숨바꼭질 3 - javascript

📌 문제

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

📌 풀이

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

const [start, end] = input[0].split(" ").map(Number);
const bfs = () => {
  const q = [[start, 0]];
  const visited = new Array(100001).fill(false);
  visited[start] = true;

  while (q.length) {
    const [position, time] = q.shift();

    if (position === end) {
      console.log(time);
      return;
    }

    for (let next of [position * 2, position - 1, position + 1]) {
      if (next < 0 || next > 100000 || visited[next]) continue;

      if (next === position * 2) {
        q.unshift([next, time]);
      } else {
        q.push([next, time + 1]);
      }
      visited[next] = true;
    }
  }
};

bfs();

✔️ 알고리즘 : BFS

✔️ 2배로 순간이동할때 시간이 증가되지 않는 점에 유의해야 한다.

✔️ bfs탐색 배열에 넣어줄 때 순간이동 했을 경우를 먼저 탐색해야하므로 unshift 로 맨앞에 넣어주고 그 외의 경우에는 push로 일반적인 순서에 맞게 넣어준다.

✔️ 방문배열을 설정하여 이미 탐색한 위치는 continue하도록 한다.

✔️ 난이도 : 백준 기준 골드 5