백준1326 - 폴짝폴짝 (BFS) node.js

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

해당 문제는 BFS 알고리즘으로 해결할 수 있는 문제다.

 a가 꼭 b보다 작다는 조건이 없기 때문에, 양쪽 방향으로 모두 이동이 가능하다는 점을 주의하면 된다.

다만 먼저 방문처리를 하지 않으면 queue에 삽입되는 원소가 많아 시간이 오래 걸릴 수 있으므로

queue 삽입 전 방문 처리를 하는 방식으로 처리하는 것이 좋아보여 아래와 같이 로직을 작성했다.

 

전체 소스 코드

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

function solution(data) {
  const [[N], arr, [start, end]] = data.map((el) => el.split(" ").map(Number));

  const visited = Array.from({ length: N }, () => -1);
  visited[start - 1] = 0;

  const queue = [[start - 1, 0]];
  let queueIdx = 0;

  while (queueIdx < queue.length) {
    const [node, cnt] = queue[queueIdx++];

    const dist = arr[node];

    let minus = node,
      plus = node;

    while (true) {
      minus -= dist;
      if (minus < 0) break;
      if (visited[minus] == -1) {
        visited[minus] = cnt + 1;
        queue.push([minus, cnt + 1]);
      }
    }

    while (true) {
      plus += dist;
      if (plus >= N) break;
      if (visited[plus] == -1) {
        visited[plus] = cnt + 1;
        queue.push([plus, cnt + 1]);
      }
    }
  }
  console.log(visited[end - 1]);
}

solution(input);