다익스트라 처음 써봐서 원리 알아가고 있는 단계임

크게 두 가지 질문이 있는데 도와주면 정말 고맙겠음...


1. 백준 1753번 최단경로 문제 (링크) 를 맞췄는데, 시간 초과가 났어야 할 코드가 왜 여유롭게 맞는지 모르겠음

언어는 JavaScript고, JavaScript는 힙 라이브러리가 없으므로 직접 구현해서 코드는 49번째 줄부터 보면 돼

주석 처리한 55번째 줄은 이미 방문한 지점 또 비효율적으로 탐색하지 않도록 입구컷 시키는 코드거든

그런데 왜인지 저 부등호 방향을 다르게 하든, 저 코드를 주석 처리해서 작동하지 않게 해도 1000ms(JS는 시간제한 5초) 내외로 여유롭게 통과하고 있음

다른 사람들 제출한 코드보면 대부분 저 입구컷 시키는 코드를 넣고 있거든, 그런데 왜 난 저걸 넣든 말든 차이가 없는건지를 모르겠음

내 코드는 방문처리 하는 역할의 코드가 없는데 왜 이게 통과했는지 모르겠음


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// 이건 그냥 힙 구현한 거니 무시해도 상관 없을 듯
class Heap {
  constructor() {
    this.heap = [];
  }
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
  push(item) {
    this.heap.push(item);
    let c = this.heap.length - 1;
    let p = Math.floor((c - 1) / 2);
    while (p >= 0) {
      if (this.heap[c][1] < this.heap[p][1]) {
        this.swap(c, p);
        c = p;
        p = Math.floor((c - 1) / 2);
      }
      else break;
    }
  }
  pop() {
    if (this.heap.length === 0) return 'empty';
    else if (this.heap.length === 1) return this.heap.pop();
    this.swap(0, this.heap.length - 1);
    const popped = this.heap.pop();
    let c = 0;
    let p = 1;
    while (p < this.heap.length) {
      if (this.heap[c][1] > this.heap[p][1] || (this.heap[p + 1] !== undefined && this.heap[c][1] > this.heap[p + 1][1])) {
        if (this.heap[p + 1] === undefined || this.heap[p][1] < this.heap[p + 1][1]) {
          this.swap(c, p);
          c = p;
          p = p * 2 + 1;
        }
        else {
          this.swap(c, p + 1);
          c = p + 1;
          p = (p + 1) * 2 + 1;
        }
      }
      else break;
    }
    return popped;
  }
}
 
// 사실상 여기부터 검토해야 할 부분임
function dijkstra(start) {
  let queue = new Heap();
  queue.push([start, 0]);
  dist[start] = 0;
  while (queue.heap.length > 0) {
    const [v, d] = queue.pop();
    // if (d > dist[v]) continue; <-- 이 주석문
    for (let i = 0; i < graph[v].length; i++) {
      nextV = graph[v][i][0];
      nextD = graph[v][i][1];
      let cost = d + nextD;
      if (cost < dist[nextV]) {
        dist[nextV] = cost;
        queue.push([nextV, cost]);
      }
    }
  }
}
 
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [vertex, edge] = input[0].split(' ').map((x) => parseInt(x));
const start = parseInt(input[1]);
const INF = 99999999;
let dist = new Array(vertex + 1).fill(INF);
let visited = new Array(vertex + 1).fill(false);
let graph = new Array(vertex + 1);
for (let i = 1; i <= vertex; i++) {
  graph[i] = [];
}
for (let i = 2; i < edge + 2; i++) {
  const [s, e, d] = input[i].split(' ').map((x) => parseInt(x));
  graph[s].push([e, d]);
}
dijkstra(start);
 
result = '';
for (let i = 1; i <= vertex; i++) {
  if (dist[i] === 99999999) dist[i] = 'INF';
  result += dist[i] + '\n';
}
 
console.log(result);
 
 
cs


2. 다익스트라에서 다음 간선을 고를 때, 항상 정점의 거리가 최소인 간선을 우선적으로 찾는 이유를 정확히 모르겠음

정점의 거리가 최소인 간선부터 찾든 그렇지 않든 결국 모든 정점을 찾게 되니까 답은 똑같이 나오지 않음?

물론 시간은 더 오래 걸리긴 했으니 우선적으로 찾지 않는다면 시간이 더 걸릴 거라는 건 알겠는데, 백준 질문 게시판에서 이렇게 하지 않으면 틀릴 수도 있다는 글을 보고 의문이 들었음

최소 힙은 그래도 알고 있어서 그걸로 구현하기는 했다만 이유를 알아야 다음에 응용 문제를 풀 때 안 막힐 것 같음