[백준] 13913번: 숨바꼭질 4 - Node.js (자바스크립트)

1. 문제 ㅡ 13913번: 숨바꼭질 4 (난이도: Gold IV)

13913번: 숨바꼭질 4

 

2. 풀이 ㅡ Node.js (자바스크립트)

const [subin, sister] = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(val => +val);

const visited = Array.from({ length: 100001 }, () => false);
const path = Array.from({ length: 100001 }, () => -1);

const moveSubin = N => {
  const queue = [[N, 0]];
  visited[N] = true;

  while (queue.length) {
    const [current, time] = queue.shift();

    if (current === sister) return time;

    [current - 1, current + 1, current * 2].forEach(move => {
      if (visited[move] || move < 0 || move > 100001) return;

      visited[move] = true;
      path[move] = current;

      queue.push([move, time + 1]);
    });
  }
};

const minimunTime = moveSubin(subin);

const order = [sister];
let previous = path[sister];

for (let i = 0; i < minimunTime; i++) {
  order.push(previous);

  previous = path[previous];
}

console.log(minimunTime);
console.log(order.reverse().join(' '));

 

2-1. 풀이 설명

숨바꼭질, 숨바꼭질 3에 이어 세 번째로 풀어본 숨바꼭질 시리즈 문제다. 이번 문제에서는 수빈이가 동생을 찾는 데까지 걸리는 최단시간은 물론, 수빈이 이동한 경로를 출력해야 한다. 물론 스페셜 저지 문제이기 때문에 경로가 달라도 정답으로 인정된다. 

 

BFS 탐색은 다른 숨바꼭질 문제들과 동일한 방법으로 접근했다. 문제는 수빈이가 동생을 찾았을 때까지 이동한 경로를 다 알고있어야 한다는 점이었다. 처음에는 queue에 넣어주는 배열 자체를 객체로 변경하고, 각 객체 별로 누적된 이동 경로 정보를 가지고 있는 path 배열을 갖고 있도록 했다. 이렇게 했더니 바로 메모리 초과가 떴다. 

 

그래서 확인 여부를 확인하기 위해 checked 배열을 사용한 것처럼, 이동 경로를 기록해두기 위해 전역 환경에 path 라는 배열을 만들어두었다. 이후 수빈의 다음 위치를 탐색할 때마다 해당 위치를 어디서 온 건지 저장해두고 (위 코드의 경우 반복문 안에서 유효한 move를 확인할 때마다 path에 current 값을 넣어줬다) 추후 BFS 탐색이 완료된 후 역추적해서 이동 경로를 확인했다.