백준5014 - 스타트링크 (BFS) node.js

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

해당 문제는 전체 층수, 시작 위치, 목적지, 업버튼으로 오를 수 있는 층수, 다운버튼으로 내려갈 수 있는 층수가 주어졌을 때, 최소 몇번으로 목적지에 도착할 수 있는지 묻는다.

 

문제 풀이 방식

최소 몇번으로 도착하는지 묻기 때문에, BFS 알고리즘으로 접근했다.

처음 시작 위치로 시작하여, 해당 위치에 이미 방문했는지 여부를 검증함으로써 시간복잡도를 줄이고,

다음 올라가거나 내려가는 위치가 올바른 위치인지 검증한 후 대기열(queue)에 추가하는 방식으로 문제를 해결하였다.

 

처음 위치와 목적지가 같을 수 있다는 것만 주의하면 어렵지 않다.

 

전체 소스 코드

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

function solution(data) {
  const [F, S, G, U, D] = data[0].split(" ").map(Number);

  const queue = [[S, 0]];
  let queueIdx = 0;
  let result = null;
  const visited = {};

  while (queueIdx < queue.length) {
    const [node, cnt] = queue[queueIdx++];
    if (node === G) {
      result = cnt;
      break;
    }

    if (visited[node]) continue;

    visited[node] = true;
    const [nextUp, nextDown] = [node + U, node - D];

    if (F >= nextUp) queue.push([nextUp, cnt + 1]);
    if (nextDown >= 1) queue.push([nextDown, cnt + 1]);
  }

  console.log(result !== null ? result : "use the stairs");
}

solution(input);