백준 9019 < DSLR > JavaScript

📍문제 링크

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

9019번: DSLR

 

📍알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색

 

📍문제 풀이

- DSLR 연산

D : n을 2배로 바꾼다. 결과값이 9999보다 큰 경우에는, 10000 으로 나눈 나머지를 취한다

S : n에서 1을 뺀다 (0이면 9999로 변함)

L : 각 자릿수를 왼쪽으로 1칸 옮김

R : 각 자릿수를 오른쪽으로 1칸 옮김

 

- 0~9999인 두 수 A, B가 주어질 때, A를 B로 바꾸는 최소한의 명령어 나열을 구하라

 

📍의사 코드

BFS 함수를 구성

 

📍코드 (JavaScript)

const [in1, ...in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const tNum = +in1;
const data = in2.map((el) => el.split(" ").map(Number));
const answer = [];

const bfs = (A, B) => {
  const queue = [[A, ""]];
  const isVisited = { [A]: true };

  while (queue.length) {
    const [num, order] = queue.shift();

    if (num === B) {
      answer.push(order);
      return;
    }

    // D
    const newD = (num * 2) % 10000;
    if (!isVisited[newD]) {
      queue.push([newD, order + "D"]);
      isVisited[newD] = true;
    }

    // S
    const newS = num === 0 ? 9999 : num - 1;
    if (!isVisited[newS]) {
      queue.push([newS, order + "S"]);
      isVisited[newS] = true;
    }

    // L
    const newL = (num % 1000) * 10 + Math.floor(num / 1000);
    if (!isVisited[newL]) {
      queue.push([newL, order + "L"]);
      isVisited[newL] = true;
    }

    // R
    const newR = (num % 10) * 1000 + Math.floor(num / 10);
    if (!isVisited[newR]) {
      queue.push([newR, order + "R"]);
      isVisited[newR] = true;
    }
  }
};

for (let el of data) {
  const [A, B] = el;
  bfs(A, B);
}

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

 

📍리뷰

- 4자리 숫자(abcd)를 나타내는 표현

(((a * 10 + b) * 10 + c) * 10 + d)

 

- 4자리 숫자의 자릿수를 왼쪽, 오른쪽으로 옮기는 것은 코드 한 줄로 가능!

- 큐를 연결리스트로 바꾸면 더 빠르게 해결 가능