[백준5014_자바스크립트(javascript)] - 스타트링크

🔴 문제

스타트링크

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [f, s, g, u, d] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split(' ')
  .map(Number);

const floors = new Array(f + 1).fill(false);

floors[s] = 1;

const q = [s];
let ans = 0;

while (q.length) {
  const s = q.shift();

  if (s === g) {
    ans = floors[s];
    break;
  }

  if (s + u <= f && !floors[s + u]) {
    floors[s + u] = floors[s] + 1;
    q.push(s + u);
  }

  if (s - d >= 1 && !floors[s - d]) {
    floors[s - d] = floors[s] + 1;
    q.push(s - d);
  }
}

if (ans) console.log(ans - 1);
else console.log('use the stairs');

🟢 풀이

⏰ 소요한 시간 : 40분

최단거리를 찾는 bfs 문제유형
방문여부를 체크할 floor 배열을 만들어준다.
내가 현재 밟고있는 s층은 이미 방문한 것이므로 방문처리를 해준다. 이때 숫자로 값을 바꿔 해당 값으로 방문처리도 확인하고 버튼을 몇 번 눌렀는지 세 줄수 있도록 한다. (초기값이 1인 이유는 추후 설명)
그리고 현재 있는 층을 큐에 삽입한 뒤 큐가 빌때까지 bfs 로직을 수행해준다.
큐에서 맨 앞요소를 shift 해 현재 있는 층인 s에 할당해 주었다.
현재 있는 층 s가 목표인 g층과 같다면 ans값은 현재 내가 밟고있는 층까지 오는데 버튼을 몇번 눌렀는지 세아리는 floors[s]의 값으로 업데이트 해주고 반복을 종료한다.
만약 그게 아니라면 u버튼을 누르거나 d버튼을 누르는 연산을 해준다. 이때 확인해야 될 부분이 버튼을 눌렀을때 즉 현재 층 s와 u를 더했을 때 최고층을 넘어가지 않는지, 그리고 그 층이 미방문 상태인지 확인해서 bfs를 수행해준다. d도 마찬가지

반복을 마친후 ans를 출력해주면 되는데 ans의 초기값이 1이었기 때문에 -1을 수행해준다. 초기값을 0으로 놓지 않은 이유는 내가 있는층이 g층인경우 즉 움직일 필요가 없을 경우에는 첫 반복에서 ans값이 0인상태로 빠져나오는데 이경우에 정답을 0으로 출력해주어야 하기 때문이다.

🔵 Ref