글 읽기 - node js 우선순위 큐로 구현한 dijkstra 시간초과

alsrb0504 2년 전 0

제목 그대로 우선순위 큐(=최소힙)을 구현한 후 dijkstra 를 적용해서 게시판 내의 반례들을 모두 풀었습니다.

한 70% 쯤 넘어가더니 시간초과가 뜨네요.. ㅠㅠ

주석문 달아놓은 부분이 문제인 거 같은데

dijkstra 에서 이미 방문한 노드라도 값이 갱신되면 재방문하는 방식으로 코드를 짰는데 이 부분을 구현한 후 시간 초과가 발생했습니다..

다시 방문하는 조건이 틀린 걸까요..?

const readFileSyncAddress = '/dev/stdin';

let input = require("fs")
  .readFileSync(readFileSyncAddress)
  .toString()
  .split("\n");

const INF = Infinity;

const [v, e] = input[0].trim().split(" ").map(Number);
const begin = Number(input[1]);
const g = Array.from({ length: v + 1 }, () => []);
let dist = new Array(v + 1).fill(INF);
const visited = new Array(v + 1).fill(false);

let result = "";

for (let i = 2; i < 2 + e; i++) {
  const [u, v, cost] = input[i].split(" ").map(Number);

  g[u].push([v, cost]);
}

class MinHeap {
  constructor() {
    this.heap = [null];
  }

  getMin() {
    return this.heap[1] ? this.heap[1] : null;
  }

  size() {
    return this.heap.length - 1;
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  push(value) {
    this.heap.push(value);
    let curIdx = this.heap.length - 1;
    let parIdx = Math.floor(curIdx / 2);

    while (curIdx > 1 && this.heap[parIdx].cost > this.heap[curIdx].cost) {
      this.swap(curIdx, parIdx);
      curIdx = parIdx;
      parIdx = Math.floor(curIdx / 2);
    }
  }

  pop() {
    const min = this.heap[1];
    if (this.heap.length <= 2) this.heap = [null];
    else this.heap[1] = this.heap.pop();

    let curidx = 1;
    let leftidx = curidx * 2;
    let rightidx = curidx * 2 + 1;

    if (!this.heap[leftidx]) return min;
    if (!this.heap[rightidx]) {
      if (this.heap[leftidx].cost < this.heap[curidx].cost) {
        this.swap(leftidx, curidx);
      }
      return min;
    }

    while (
      leftidx < this.size() &&
      (this.heap[leftidx].cost < this.heap[curidx].cost ||
        this.heap[rightidx].cost < this.heap[curidx].cost)
    ) {
      const minidx =
        this.heap[leftidx].cost > this.heap[rightidx].cost ? rightidx : leftidx;
      this.swap(minidx, curidx);
      curidx = minidx;
      leftidx = curidx * 2;
      rightidx = curidx * 2 + 1;
    }

    return min;
  }
}

// console.table(g);

function dijkstra(start) {
  dist[start] = 0;
  visited[start] = true;

  const minHeap = new MinHeap();
  minHeap.push({
    vertex: start,
    cost: 0,
  });

  while (minHeap.size() > 0) {
    const { vertex, cost } = minHeap.pop();
    visited[vertex] = true;

    for (let i = 0; i < g[vertex].length; i++) {
      const cur = g[vertex][i];
      const next = cur[0];
      const nextCost = cur[1];

      // 방문한 값이더라도 값이 값이 갱신되면 다시 방문 => 시간초과
      let reVisit = false;

      if (dist[next] > dist[vertex] + nextCost) {
        dist[next] = dist[vertex] + nextCost;

        reVisit = true;
      }

      if (visited[next] && !reVisit) continue;

      minHeap.push({ vertex: next, cost: nextCost });
    }
  }
}

dijkstra(begin);

for (let i = 1; i <= v; i++) {
  if (dist[i] === Infinity) {
    result += "INF\n";
  } else {
    result += dist[i] + "\n";
  }
}

console.log(result.trimEnd());

slah007 2년 전 2

다익스트라 알고리즘은 우선순위 큐를 써서 거리가 짧은 순으로 방문하기 때문에 한 번 방문한 정점을 다시 방문했을 때 인접한 정점의 거리를 더 짧게 갱신할 가능성이 없고, 다시 방문했을 때는 인접 정점을 순회하지 않아도 괜찮습니다. 이러한 재방문은 최악의 경우 V^2번 연산을 필요로 하게 만들어 시간 초과를 받는 것 같습니다.

alsrb0504 2년 전 0

감사합니다. 하나씩 그려보면서 확인했더니 인접한 거리를 더 짧게 갱신하는 일이 없네요.

덕분에 해결했습니다. ㅎㅎ

function dijkstra(start) {
  dist[start] = 0;
  visited[start] = true;

  const minHeap = new MinHeap();
  minHeap.push({
    vertex: start,
    cost: 0,
  });

  while (minHeap.size() > 0) {
    const { vertex, cost } = minHeap.pop();
    visited[vertex] = true;

    for (let i = 0; i < g[vertex].length; i++) {
      const cur = g[vertex][i];
      const next = cur[0];
      const nextCost = cur[1];

      // 이미 방문한 값이라면 pass
      if (visited[next]) continue;

      // 미방문 값이라면
      if (dist[next] > dist[vertex] + nextCost) {
        dist[next] = dist[vertex] + nextCost;

        // 값이 갱신되는 경우에만 push
        minHeap.push({ vertex: next, cost: dist[vertex] + nextCost });
      }
    }
  }
}

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

문제

문제

출처

ICPC

node js 우선순위 큐로 구현한 dijkstra 시간초과

alsrb0504 2년 전 0

slah007 2년 전 2

alsrb0504 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말