[백준] 9019 DSLR - javascript

📌 문제

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

📌 풀이

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

input.shift();
const ans = [];
const bfs = (start, end) => {
  const visited = Array.from({ length: 10000 }, () => false);
  visited[start] = true;
  const queue = [[start, ""]];

  while (queue.length) {
    let [cur, path] = queue.shift();
    if (cur === end) {
      ans.push(path);
      return;
    }

    const nextD = (cur * 2) % 10000;
    if (!visited[nextD]) {
      visited[nextD] = true;
      queue.push([nextD, path + "D"]);
    }

    const nextS = cur === 0 ? 9999 : cur - 1;
    if (!visited[nextS]) {
      visited[nextS] = true;
      queue.push([nextS, path + "S"]);
    }

    const nextL = (cur % 1000) * 10 + Math.floor(cur / 1000);
    if (!visited[nextL]) {
      visited[nextL] = true;
      queue.push([nextL, path + "L"]);
    }

    const nextR = (cur % 10) * 1000 + Math.floor(cur / 10);
    if (!visited[nextR]) {
      visited[nextR] = true;
      queue.push([nextR, path + "R"]);
    }
  }
};
input.map((i) => {
  const [start, end] = i.split(" ").map(Number);
  bfs(start, end);
});

console.log(ans.join("\n"));

✔️ 알고리즘 : BFS

✔️ 다음 단계로 넘어갈 때 총 4가지의 경우의 수가 있다. visited 배열을 통해 방문한 좌표인지 체크하고 방문하지 않았을 경우에만 bfs탐색을 이어간다.

✔️ path를 저장하기 위해 queue에 삽입할 때 좌표와 현재까지의 경로를 string 타입 값으로 넣어주었다.

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