[JS][백준]1753_최단경로

문제 번호

1753번: 최단경로

 

 

 

알고리즘 분류

• 그래프 이론
• 다익스트라

 

문제 풀이

 다익스트라 알고리즘을 사용해야한다. 그리고 다익스트라 알고리즘을 사용하기위해서 heap자료구조를 알아야한다. 이 문제에서는 MaxHeap이 아닌 MinHeap을 사용할것이다. 

 알고리즘 자체에 대한 설명이나 Heap 자체에 대한 설명은 더 좋은 블로그들이 많이 있으므로 따로 작성하진 않는다.

 

다익스트라.

23. 다익스트라(Dijkstra) 알고리즘

힙.

[자료구조] 힙 (Heap) or 이진 힙(binary heap)

 

 해당 문제를 풀기전에 

11279번: 최대 힙

 

1927번: 최소 힙

 두개의 힙 문제를 풀어봄으로 인해서 다익스트라에서 사용할 힙에 문제가 없음을 확인하였다.

그런데 분명 같은코드를 사용했음에도 다익스트라 코드에서는 타입에러가 계속 발생하였다.

아마 다익스트라 코드에서는 객체의 값에 접근해야해서 그런걸로 생각된다...(아직 정확하게 모르겠음).

 그래서 '1927번 최소힙' 문제를 풀떄 제출했던 최소 힙 구현 코드에 한줄을 추가하면 타입에러 없이 문제를 해결할 수 있다는것을 발견했다.

 

  heappop() {
    const min = this.heap[1]; // minHeap 이니까 가장 위의 원소가 제일 작다.
    if (this.heap.length <= 2) this.heap = [null]; // 원소가 1개만 남아있을때 pop 하면 아무것도 남지않는다.
    else this.heap[1] = this.heap.pop();  // 가장 아래있던 원소를 가장 위로 올려놓고 정렬해야한다.

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

    // 가장 위로 올린원소를 정렬해야한다.    
    if (!this.heap[left]) return min; // left 자식이 없다는것은 자식이 존재하지 않는다는것을 의미한다.
    if (!this.heap[right]) { // right 자식이 없는경우.
      if (this.heap[left] < this.heap[cur]) {
        this.swap(left, cur);
      }
      return min;
    }
    while ( this.heap[left] < this.heap[cur] || this.heap[right] < this.heap[cur]) { // 자식중에 현재 원소보다 큰 값이 없을때 까지 swap해주면서 정렬한다.
      let minIdx = this.heap[left] > this.heap[right] ? right : left; // 두개의 자식중에 더 큰값을 찾아야한다.
      this.swap(minIdx, cur);
      cur = minIdx;
      left = cur * 2;
      right = cur * 2 + 1;
    }
    return min;
  }
}

 이것이 기존의 '1927번 최소힙'에 제출한 코드의 pop() 부분이다.

 

heappop() {
    const min = this.heap[1]; // minHeap 이니까 가장 위의 원소가 제일 작다.
    if (this.heap.length <= 2) this.heap = [null]; // 원소가 1개만 남아있을때 pop 하면 아무것도 남지않는다.
    else this.heap[1] = this.heap.pop();  // 가장 아래있던 원소를 가장 위로 올려놓고 정렬해야한다.

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

    // 가장 위로 올린원소를 정렬해야한다.    
    if (!this.heap[left]) return min; // left 자식이 없다는것은 자식이 존재하지 않는다는것을 의미한다.
    if (!this.heap[right]) { // right 자식이 없는경우.
      if (this.heap[left].cost < this.heap[cur].cost) {
        this.swap(left, cur);
      }
      return min;
    }
    while(left < this.size() && (this.heap[cur].cost > this.heap[left].cost || this.heap[cur].cost > this.heap[right].cost)) { // 자식중에 현재 원소보다 큰 값이 없을때 까지 swap해주면서 정렬한다.
      let minIdx = this.heap[left].cost > this.heap[right].cost ? right : left; // 두개의 자식중에 더 큰값을 찾아야한다.
      this.swap(cur, minIdx);
      cur = minIdx;
      left = cur * 2;
      right = cur * 2 + 1;
    }
    return min;
  }
}

그리고 이게 다익스트라 문제에 제출한 코드의 pop() 부분이다.

 

MinHeap 코드

다익스트라 코드

 

차이점은 whie문 속에 ` left < this size() && ` 를 추가해준것이다. 그리고 뒤에 따라오는 this.heap[cur].cost........ 조건도 괄호로 묶어주어야한다. 안묶으면 오답이다.

 

 막상 다익스트라 알고리즘 자체는 어렵지 않았다.

처음에는 (문제에서 주어질 수 있는 최대 정점의 갯수) ^2 크기의 2차원 배열을 만들어서 문제를 입력받으려고 했다. 그런데 최대 정점의 갯수가 20000개 이므로 20000^2 크기의 2차원 배열을 만들면 메모리를 초과하게 된다. 그래서 C++ 에서 Vector를 사용했을 때 처럼 문제에서 주어진 간선정보만 입력받아서 처리해주기로 했다.

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);
}

' u에서 v로 갈떄 w만큼의 비용이 든다 ' 라는 정보를 graph[u]에 담는다.

 

이후엔 그냥 다익스트라 알고리즘을 적용하면된다.

function dijkstra() {
  let answer = '';
 
  let pq = new minHeap();
  pq.add({ node: K, cost: 0 }); // 도착점, 비용.
  d[K] = 0;
    
  while (pq.size() !== 0) {

    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());
}

 앞서 기술했던 heap의 타입에러를 해결하려고 이것저것 해보다가 잘못구현한 heap으로도 다익스트라 알고리즘이 작동하는것을 보았다. Minheap에 1 2 3 순서로 값을 넣고 3번의 pop을 했을때 1 2 3 이 아니라 1 3 2 순서로 pop 되었는데도 정답처리를 받은것이다.

처음에는 의아했는데 다익스트라에서 Minheap을 이용하는 목적이 업데이트의 개수를 최소하기 위해서라는걸 생각해보면 Minheap의 순서가 조금 틀려도 정답을 받는데는 상관이 없다는걸 알 수 있었다. 물론 정상적인 Minheap보다 성능은 조금 떨어진다. 

 

 아무튼 1927번 문제와 해당 다익스트라 문제를 계속 왔다갔다 하면서 최소힙 문제에서도 정답을 받고, 다익스트라 문제에서도 정답을 받은 코드는 다음과같다.

 

전체코드

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.heap = [null];
  }
  size() {
    return this.heap.length - 1;
  }
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
  add(value) {
    this.heap.push(value);
    let cur = this.heap.length - 1; // 제일 나중 노드에 새로 들어온 원소를 추가한다.
    let parent = Math.floor(cur / 2);

    while (cur > 1 && this.heap[parent].cost > this.heap[cur].cost) {  // 
      this.swap(cur, parent);
      cur = parent;
      parent = Math.floor(cur / 2);
    }
  }
  heappop() {
    const min = this.heap[1]; // minHeap 이니까 가장 위의 원소가 제일 작다.
    if (this.heap.length <= 2) this.heap = [null]; // 원소가 1개만 남아있을때 pop 하면 아무것도 남지않는다.
    else this.heap[1] = this.heap.pop();  // 가장 아래있던 원소를 가장 위로 올려놓고 정렬해야한다.

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

    // 가장 위로 올린원소를 정렬해야한다.    
    if (!this.heap[left]) return min; // left 자식이 없다는것은 자식이 존재하지 않는다는것을 의미한다.
    if (!this.heap[right]) { // right 자식이 없는경우.
      if (this.heap[left].cost < this.heap[cur].cost) {
        this.swap(left, cur);
      }
      return min;
    }
    while(left < this.size() && (this.heap[cur].cost > this.heap[left].cost || this.heap[cur].cost > this.heap[right].cost)) { // 자식중에 현재 원소보다 큰 값이 없을때 까지 swap해주면서 정렬한다.
      let minIdx = this.heap[left].cost > this.heap[right].cost ? right : left; // 두개의 자식중에 더 큰값을 찾아야한다.
      this.swap(cur, minIdx);
      cur = minIdx;
      left = cur * 2;
      right = cur * 2 + 1;
    }
    return min;
  }
}

function dijkstra() {
  let answer = '';
 
  

  let pq = new minHeap();
  pq.add({ node: K, cost: 0 }); // 도착점, 비용.
  d[K] = 0;
    
  while (pq.size() !== 0) {

    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();

 

특이사항

 왜 TypeError가 나는지 정확하게 모르겠다.