[알고리즘/백준/13549] 숨바꼭질 3(BFS, 우선순위 큐, Nodejs)

문제

---

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

13549번: 숨바꼭질 3

 

풀이

---

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [N, K] = fs.readFileSync(filePath).toString().trim().split(" ").map(Number);
const MAX = 100001;
const ch = Array.from({ length: MAX }, () => 0);

// 시간 증가하지 않는 경우(x*2)가 우선순위가 높다 -> q의 앞에 넣기
function bfs() {
  const q = [[N, 0]]; // [위치, 시간]
  ch[N] = 1;

  while (true) {
    const [cur, time] = q.shift();
    if (cur === K) return time;

    for (let nx of [cur - 1, cur + 1, cur * 2]) {
      if (ch[nx] === 1 || nx < 0 || nx >= MAX) continue;

      if (nx === cur * 2) q.unshift([nx, time]); // x*2로 이동 시에 시간 증가 X
      else q.push([nx, time + 1]); // x-1, x+1로 이동 시 시간 증가 O
      ch[nx] = 1;
    }
  }
}

console.log(bfs());

수빈이가 N에서 동생 위치 K까지 가는 최소 시간을 구하는 문제이다. 

X에서 이동 가능한 위치는 1초 후 X-1, X+1, 또는 0초 후 X*2이다. 

 

순간 이동(0초 소요)이 걷는 이동(1초 소요)보다 빠르기 때문에 우선 순위가 높다. 이 문제는 기존 BFS와 달리 모든 간선의 가중치가 동일하지 않다. 따라서 우선순위가 높은 정점(X*2)을 큐의 뒤가 아닌 앞에 넣어 먼저 탐색하는 방법을 사용할 수 있다. 처음에는 이것을 생각하지 않고 모두 push를 통해 순서대로 큐에 넣어 탐색했더니 해결되지 않았다. 

 

이를 위해 양 쪽 끝에서 삽입과 삭제가 모두 가능한 deque 자료구조가 필요하다. 자바스크립트에서는 덱을 구현할 때 빈 배열을 선언하고, unshift, shift, push, pop 메서드를 사용한다. 

 

또 현재 위치까지 걸린 시간을 저장할 배열을 따로 사용하지 않고(메모리 초과...), 덱에 함께 기록해 활용한다.

 

(2023/8/23 수정) 시간을 구하는 배열을 따로 사용했을 때 메모리 초과가 뜬 이유는 ch 배열로 방문 확인을 해주지 않았기 때문이다. 우선 순위 큐를 사용했을 때 x*2, 즉 순간 이동을 우선적으로 하고 순간 이동한 위치에서 이동 가능한 위치를 먼저 확인한다. 따라서 최단 거리를 먼저 기록하기 때문에 방문한 노드는 다시 방문할 필요가 없다. 

 

아래와 같이 현재 위치까지 걸린 시간을 저장할 배열을 따로 만들어 풀 수도 있다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [N, K] = fs.readFileSync(filePath).toString().trim().split(" ").map(Number);

const MAX = 100000 + 1;
const ch = Array.from({ length: MAX }).fill(0);
const dis = Array.from({ length: MAX }).fill(0);

function BFS() {
  const queue = [];
  queue.push(N);
  ch[N] = 1;

  while (true) {
    const x = queue.shift();
    if (x === K) return dis[x];

    for (let nx of [x - 1, x + 1, x * 2]) {
      if (nx < 0 || nx >= MAX || ch[nx] === 1) continue;

      if (nx === x * 2) {
        if (nx === K) return dis[x];
        dis[nx] = dis[x];
        queue.unshift(nx);
      } else {
        if (nx === K) return dis[x] + 1;
        dis[nx] = dis[x] + 1;
        queue.push(nx);
      }
      ch[nx] = 1;
    }
  }
}

console.log(BFS());