글 읽기 - 다익스트라 기본문제 질문입니다 (node.js)

des0001 2년 전 0

기본 다익스트라 문제로 답은 맞췄으나 잘 이해되지 않는 부분이 있습니다

소스 코드 중 inline 주석으로 감싸진 부분 109~111 라인

if (dist[src] !== w) {
continue;
}

이 부분인데요

1753 문제에서는 해당 부분을 작성하지 않아도 시간 초과가 발생하지 않았으나

다른 다익스트라 유형의 문제에서는 저 윗부분이 존재하지 않으면 시간 초과가 발생하는 일이 있었습니다

그리고 저 윗부분을 넣고 안넣고 이 문제를 풀어보니 총 결과시간이 200ms 정도의 유의미한 빠름이 있기도 했습니다

근데 해당 부분이 어떤 의미인지 잘 모르겠습니다

제가 queue 에 넣을땐 w 값을 dist[src] 와 같게 넣었는데 같지 않은 경우는 어떤 경우일까요

const fs = require("fs");
let input = fs.readFileSync("./dev/stdin").toString().trim().split("\n");

const [V, E] = input
  .shift()
  .trim()
  .split(" ")
  .map((item) => parseInt(item));

const K = input.shift() * 1;

const INF = parseInt(Number.MAX_SAFE_INTEGER / 2);

input = input.map((item) =>
  item
    .trim()
    .split(" ")
    .map((ele) => parseInt(ele.trim()))
);

//최소 힙을 이용한 우선순위 큐
class MinHeap {
  constructor() {
    this.heap = [];
  }
  swap(indexA, indexB) {
    [this.heap[indexA], this.heap[indexB]] = [
      this.heap[indexB],
      this.heap[indexA],
    ];
  }
  add(dst, weight) {
    this.heap.push([dst, weight]);

    let currentIndex = this.heap.length - 1;
    let parentIndex = parseInt((currentIndex - 1) / 2);

    while (this.heap[currentIndex][1] < this.heap[parentIndex][1]) {
      this.swap(currentIndex, parentIndex);
      currentIndex = parentIndex;
      parentIndex = parseInt((currentIndex - 1) / 2);
    }
  }
  extract() {
    this.swap(0, this.heap.length - 1);
    const result = this.heap.pop();

    let currentIndex = 0;
    let leftChildIndex = 2 * currentIndex + 1;
    let rightChildIndex = (currentIndex + 1) * 2;

    while (true) {
      if (leftChildIndex >= this.heap.length) {
        break;
      }

      if (rightChildIndex >= this.heap.length) {
        if (this.heap[leftChildIndex][1] < this.heap[currentIndex][1]) {
          this.swap(leftChildIndex, currentIndex);
        }
        break;
      }
      if (
        this.heap[leftChildIndex][1] >= this.heap[currentIndex][1] &&
        this.heap[rightChildIndex][1] >= this.heap[currentIndex][1]
      ) {
        break;
      } else {
        if (this.heap[leftChildIndex][1] < this.heap[rightChildIndex][1]) {
          if (this.heap[leftChildIndex][1] < this.heap[currentIndex][1]) {
            this.swap(leftChildIndex, currentIndex);
            currentIndex = leftChildIndex;
            leftChildIndex = 2 * currentIndex + 1;
            rightChildIndex = (currentIndex + 1) * 2;
          }
        } else {
          if (this.heap[rightChildIndex][1] < this.heap[currentIndex][1]) {
            this.swap(rightChildIndex, currentIndex);
            currentIndex = rightChildIndex;
            leftChildIndex = 2 * currentIndex + 1;
            rightChildIndex = (currentIndex + 1) * 2;
          }
        }
      }
    }
    return result;
  }
  size() {
    return this.heap.length;
  }
}

function solution(arr) {
  //인접 그래프
  const graph = Array.from({ length: V + 1 }, () => []);
  //방문 체크
  const check = Array.from({ length: V + 1 }, () => 0);
  //우선순위 Queue
  const heap = new MinHeap();
  //시작점부터 n 번째 까지의 최단 거리를 담는 배열
  const dist = Array.from({ length: V + 1 }, () => INF);

  arr.forEach((v) => {
    const [src, dst, weight] = v;
    graph[src].push([dst, weight]);
  });

  heap.add(K, 0);
  dist[K] = 0;

  while (heap.size()) {
    const [src, w] = heap.extract();
    //////////////////////////////////////////////////////
    if (dist[src] !== w) {
      continue;
    }
    //////////////////////////////////////////////////////
    graph[src].forEach((v) => {
      const [dst, weight] = v;
      if (check[dst] === 0 && dist[dst] > dist[src] + weight) {
        dist[dst] = dist[src] + weight;
        heap.add(dst, dist[dst]);
      }
    });
    check[src] = 1;
  }
  const answer = [];
  dist.forEach((v, k) => {
    if (k) {
      if (v === INF) {
        answer.push("INF");
      } else {
        answer.push(v);
      }
    }
  });
  console.log(answer.join("\n"));
}

solution(input);

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

문제

문제

출처

ICPC

다익스트라 기본문제 질문입니다 (node.js)

des0001 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말