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

백준 폴짝폴짝 문제입니다.
solve.ac 기준 실버2 BFS 문제입니다.
며칠동안 끙끙거리다가 실수를 찾아내 기록합니다.

문제

해당 칸의 숫자의 배수만큼 좌우로 점프할 때, start에서 end로 몇번의 점프만의 도달할 수 있는지 구하는 문제입니다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt";

let [n, bridge, goal] = fs.readFileSync(filePath).toString().trim().split("\n");
n = Number(n);
bridge = bridge.split(" ").map(Number);
let [start, end] = goal.split(" ").map(Number);

console.log(solution(start, end));

function solution(start, end) {
  const record = Array(n + 1).fill(0);
  record[start] = 1;
  const q = [[start, 1]];

  while (q.length) {
    const [node, count] = q.shift();
    let i = node % bridge[node - 1];
    // i = 0일 때, index 0을 사용하지 않으니까 이렇게 처리
    if (!i) i += bridge[node - 1];

    while (i <= n) {
      check(record, q, i, count);
      if (record[end]) {
        // 성공시
        // console.log(record);
        return record[end] - 1;
      }
      i += bridge[node - 1];
    }
  }
  // 실패시
  // console.log(record);
  return -1;
}

function check(record, q, i, count) {
  if (!record[i]) {
    record[i] = count + 1;
    q.push([i, count + 1]);
  }
}

/*
최소 몇번의 점프로 도착지에 갈 수 있는가? => BFS로 count 세기

좌우 방향으로 그칸의 배수만큼 이동
*/

풀이

문제를 보고 요구사항을 먼저 정리했습니다.
최소 몇번의 점프로 도착지에 갈수 있는지 묻는 문제이므로 BFS로 점프횟수를 count해서 저장하고, 좌우 방향으로 그칸의 배수만큼 이동합니다.

정리

가장 처음 놓친것이 1 => 3처럼 최종적으로 오른쪽으로만 이동하는줄 알았습니다.
start < end라고 안써있었는데 그냥 저도 모르게 그렇게 생각했습니다.

두번째 놓친것이 end까지 for문은 돌리는데 안으로 들어가질 않았습니다.
원인이 end가 작을때인듯 하여 Math.max(start, end)까지 돌렸는데
사실 다리 끝까지가야하니까 입력된 n까지 돌리는게 맞았습니다.

요구사항을 읽으면서 어떻게 풀지 생각할 때 주어진 조건들을 더 따져보자