[백준1697_자바스크립트(javascript)] - 숨바꼭질

🔴 문제

숨바꼭질

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split(' ')
  .map((it) => Number(it));
let n = inputs[0];
const k = inputs[1];
const map = new Array(100001).fill(0);

const q = [n];

while (q.length) {
  const target = q.shift();
  if (target === k) {
    console.log(map[target]);
    break;
  }

  for (const newTarget of [target - 1, target + 1, target * 2]) {
    if (newTarget >= 0 && newTarget <= 100000 && map[newTarget] === 0) {
      map[newTarget] = map[target] + 1;
      q.push(newTarget);
    }
  }
}

🟢 풀이

최단 거리를 찾는 문제이기 때문에 bfs로 풀이한다.
시작 좌표값을 큐에 넣고 큐가 빌때까지 반복해주면 된다.

• 목적지에 도달했다 -> 정답 출력 후 반복문 탈출
• 목적지에 도달하지 못했다. -> 범위와 방문 여부 체크 후 방문처리/큐에 삽입
  dfs/bfs가 가장 기본유형인데 왤케 어려운지 모르겠다...
  앞으로 문제의 방향성을 dfs또는 bfs로 확정했을 경우 내가 생각한대로 코드를 구현해나가지 않고 무조건 기본 공식에서 응용해 나가야겠다.
  
  

🔵 Ref

https://chancoding.tistory.com/193