글 읽기 - 잘못 구현한 min heap을 사용했는데 맞았습니다.

naverstop 2년 전 0

Node js로 minheap을 구현하여 문제를 풀었는데 정답처리를 받았습니다.

그런데 min heap 에 1 2 3 순서대로 add(추가)를 진행하고 3번 heappop(제거)를 진행하니 1 2 3 순서가 아니라 1 3 2 순서로 출력이 되는것을 확인했습니다.

그래서 1927번 문제 '최소 힙' 에 minheap 부분만 떼어내서 제출해본 결과 오답이 나왔습니다.

제가 다익스트라 알고리즘을 잘 모르는건가요?

알려주시면 감사하겠습니다!

const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
let [V, E] = input[0].trim().split(' ').map(Number);
let K = +input[1];
let graph = new Array(V + 1).fill(null).map(_ => new Array());
let d = new Array(V + 1).fill(Infinity); // 각 노드까지의 최소경로.

class minHeap {
  constructor() {
      this.nodes = []
  }
  add(value) {
      this.nodes.push(value)
      this.bubbleUp()
  }
  bubbleUp(index = this.nodes.length - 1) {
      if (index < 1) return;

      const currentNode = this.nodes[index]
      const parentIndex = Math.floor((index - 1) / 2)
      const parentNode = this.nodes[parentIndex]
      if (parentNode.cost <= currentNode.cost) return;

      this.nodes[index] = parentNode
      this.nodes[parentIndex] = currentNode
      index = parentIndex
      this.bubbleUp(index)
  }
  heappop() {
      const min = this.nodes[0]
      if(this.nodes.length === 1){
          this.nodes.pop();
          return min;
      };
      this.nodes[0] = this.nodes.pop()
      this.trickleDown();
      return min
  }
  trickleDown(index = 0) {
      const leftChildIndex = 2 * index + 1
      const rightChildIndex = 2 * index + 2
      const length = this.nodes.length
      let minimum = index

      if(!this.nodes[rightChildIndex] && !this.nodes[leftChildIndex]) return;
      if(!this.nodes[rightChildIndex]){
          if(this.nodes[leftChildIndex].cost < this.nodes[minimum].cost){
              minimum = leftChildIndex;
          }
          return;
      }

      if(this.nodes[leftChildIndex].cost > this.nodes[rightChildIndex].cost){
          if (rightChildIndex <= length && this.nodes[rightChildIndex].cost < this.nodes[minimum].cost) {
              minimum = rightChildIndex
          }
      }else{
          if (leftChildIndex <= length && this.nodes[leftChildIndex].cost < this.nodes[minimum].cost) {
              minimum = leftChildIndex
          }
      }

      if (minimum !== index) {
          let t = this.nodes[minimum]
          this.nodes[minimum] = this.nodes[index]
          this.nodes[index] = t
          this.trickleDown(minimum)
      }
  }
}

function dijkstra(start) {
  let answer = '';

  let d = new Array(V + 1).fill(Infinity); // 각 노드까지의 최소경로.
  d[start] = 0;

  let pq = new minHeap();
  pq.add({ node: start, cost: 0 }); // 도착점, 비용.

  while (pq.nodes.length) {

    let temp = pq.heappop();
    let [cur, dist] = [temp.node, temp.cost]; // 현재 노드.    

    if (d[cur] < dist) continue;  // 최소거리가 아니면 넘어간다.
    for (let i = 0; i < graph[cur].length; i++) {
      let nextDist = dist + graph[cur][i].w;  // 다음 행선지 까지의 거리.
      if (nextDist < d[graph[cur][i].v]) {  // 거리가 더 짧으면 갱신한다.        
        d[graph[cur][i].v] = nextDist;
        pq.add({node: graph[cur][i].v, cost: nextDist}); // 다음 행선지, 지금 상태에서의 다음 행선지까지의 최소거리.
      }
    }
  }

  for (let i = 1; i <= V; i++) {
    if (d[i] === Infinity) answer += `INF\n`;
    else answer += `${d[i]}\n`;
  }

  return console.log(answer.trim());
}

function main() {
  for (let i = 0; i < E; i++) {
    let [u, v, w] = input[i + 2].trim().split(' ').map(Number);
    graph[u].push({ v: v, w: w });
  }
  dijkstra(K);
}
main();

seungwuk98 2년 전 1

다익스트라에서 heap을 사용하는 이유는 업데이트의 개수를 최소화하기 위해서입니다.

1->2 해야되는것을 1->3했다가 1->2로 한다고 해서 정답이 틀린건 아닙니다. 성능이 조금 떨어질 뿐이죠.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

잘못 구현한 min heap을 사용했는데 맞았습니다.

naverstop 2년 전 0

seungwuk98 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말