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

🔴 문제

숨바꼭질 3

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [n, k] = fs.readFileSync(path).toString().trim().split(' ').map(Number);
const SIZE = 100001;
const map = Array.from({ length: SIZE }).fill(-1);

const q = [n];
let front = 0;
map[n] = 0;
while (front < q.length) {
  const x = q[front++];

  if (x === k) {
    map[k] = map[x];
    break;
  }

  if (x * 2 < SIZE && map[x * 2] === -1) {
    q.push(x * 2);
    map[x * 2] = map[x];
  }
  if (x - 1 >= 0 && map[x - 1] === -1) {
    q.push(x - 1);
    map[x - 1] = map[x] + 1;
  }
  if (x + 1 < SIZE && map[x + 1] === -1) {
    q.push(x + 1);
    map[x + 1] = map[x] + 1;
  }
}

console.log(map[k]);

🟢 풀이

⏰ 소요한 시간 : 30분

최단 거리를 구하는 문제이므로 bfs로 풀이해야겠다고 생각했다. 좌표의 범위는 100,000까지이므로 SIZE라는 변수를 설정해서 100,001이라는 범위를 설정해줬다.
해당 사이즈로 배열을 만들어 -1로 채워준다.
그리고 시작 좌표 n을 큐에 넣어주고, 방문표시를 위해 0으로 바꿔준 뒤, bfs를 수행한다.
이 문제가 숨바꼭질과 다른 점은 순간이동은 시간소요가 되지 않는다는 점이다.
따라서 조건문 중 순간이동을 가장 위로 올려 먼저 큐에 들어갈 수 있도록 해준다.

여담이지만 3개월전의 내가 쓴 글을 보니 많이 성장한 것 같아 뿌듯하다.

🔵 Ref