[JS][백준]13549_숨바꼭질 3

문제 번호

채점 현황

 

 

 

알고리즘 분류

• 그래프 이론
• 자료 구조
• 그래프 탐색
• 너비 우선 탐색
• 다익스트라
• 0-1 너비 우선 탐색

문제 풀이

 처음에는 일반적인 BFS를 사용해서 문제를 풀려고했다. 그런데 '순간이동'시에는 시간이 증가하지 않기때문에 일반적인 BFS를 사용할 수 없었다. BFS는 가중치가 다르다는 조건을 다루기 힘들기 때문이다.

https://www.acmicpc.net/board/view/38887#comment-69010

 그래서 MinHeap을 사용해서 문제를 풀기로 하였다. 시간이 가장 적게 걸린것이 가장 처음에 오도록 MinHeap을 작성한다.

class Node {
  constructor(value, dist) {
    this.value = value;
    this.dist = dist;
  }
}
class MinHeap {
  constructor() {
    this.heap = [null];
  }
  swap(a, b) {
    [[this.heap[a], this.heap[b]]] = [[this.heap[b], this.heap[a]]];
  }
  size() {
    return this.heap.length - 1;
  }
  push(value, dist) {
    let node = new Node(value, dist);
    this.heap.push(node);
    let cur = this.heap.length - 1;
    let parent = Math.floor(cur / 2);

    while (cur > 1 && this.heap[cur].dist < this.heap[parent].dist) {
      this.swap(cur, parent);
      cur = parent;
      parent = Math.floor(cur / 2);
    }
  }
  pop() {
    let top = this.heap[1];
    if (this.heap.length <= 2) this.heap = [null];
    else this.heap[1] = this.heap.pop();

    let cur = 1;
    let left = cur * 2;
    let right = cur * 2 + 1;

    if (!this.heap[left]) return top;
    if (!this.heap[right]) {
      if (this.heap[cur].dist > this.heap[left].dist) {
        this.swap(cur, right);
      }
      return top;
    }

    while (left < this.size() && (this.heap[cur].dist > this.heap[left].dist || this.heap[cur].dist > this.heap[right].dist)) {
      let minIdx = this.heap[left].dist > this.heap[right].dist ? right : left;
      this.swap(cur, minIdx);
      cur = minIdx;
      left = cur * 2;
      right = cur * 2 + 1;
    }
    return top;
  }
}

 

 이제 BFS 처럼 현재위치에서 갈 수 있는 위치들을 탐색하여 MinHeap에 넣어주도록 하자. 이때 방문표시를 할때 주의할 점이 있었다. BFS에서는 Queue에 다음 정점을 push 하면서 visited = true 로 표시해도 됐었다. 그런데 이 문제에서는 정점을 지나갈때 visited = true 로 표시해주어야 한다. MinHeap을 pop할때 방문여부를 변경(false -> true)해야 한다는 뜻이다.

 왜냐하면 '지금위치 - 1, 지금위치 + 1, 순간이동' 을 MinHeap에 넣는 순서에따라서 최종값이 달라질 수 있기 때문이다. 순간이동은 시간을 증가시키지 않기때문에 MinHeap에서 위쪽에 위치할 가능성이 크다. 이때 방문여부를 변경해버리면 다시는 이 정점을 방문할 수 없다. 해당 정점으로 '순간이동'을 사용하지 않고 더 빠르게 올 수 있는 경우가 있게되면 해당 점점까지의 최소시간이 정상적으로 구해지지않는다.

https://www.acmicpc.net/board/view/82746

 그리고 방문여부를 나타내는 배열인 visited 배열의 크기도 100001(0~100000)이 아니라 200002로(0~200000) 해주었다. 문제에서 수빈이의 위치와 동생의 위치가 100000 이하로 주어지지만 수빈이가 이동할 수 있는 위치에는 제한이없다. 

function sol() {  
  let mh = new MinHeap();
  let visited = new Array(200002).fill(false);

  // value, dist;
  mh.push(N, 0);
  while (mh.size()) {
    let temp = mh.pop();
    let [cur, dist] = [temp.value, temp.dist];
    if (!visited[cur]) { // 안들렸던 곳이여야 한다.
      visited[cur] = true;

      if (cur === K) {
        return console.log(dist);
      }

      let next = [cur * 2, cur - 1, cur + 1];
      for (let i = 0; i < 3; i++) {
        if (!visited[next[i]] && 0 <= next[i] && next[i] <= 200002) {
          if (i === 0) { // 순간이동.
            mh.push(next[i], dist + 0);
          } else {
            mh.push(next[i], dist + 1);
          }
        }
      }
    }
  }
  console.log(answer);
}

특이사항

0 1 BFS 알고리즘도 공부해보자.

0-1 BFS(0-1 Breadth First Search)