[JS][백준]1238_파티

문제 번호

1238번: 파티

 

 

알고리즘 분류

• 그래프 이론
• 데이크스트라

 

문제 풀이

 처음엔 플로이드 와샬로 문제를 풀 수 있을 줄 알았다. 그런데 입력을 살펴보니 N의 최댓값이 1000 이였으므로 O(N^3)인 플로이드 와샬은 시간 초과에 걸림이 눈에 보였다.

 

 그렇다면 다음생각은 다익스트라였다. 각집(i)에서 X까지의 최단거리를 다익스트라를 통해서 구한다. X에서 각 집까지의 거리도 마찬가지로 다익스트라로 구하면 된다.

 

 다익스트라의 결괏값은 d라는 2차원 배열에 저장했다. d[i][j]는 i에서 j로 가는데 소모되는 최소 비용이다. 다익스트라를 구현할 줄 안다면 특별히 어려운 건 없는 문제였다.

 

전체 코드

/**
 * 플로이드와샬?
 *   10^9 라서 시간초과다.
 * 다익스트라를 이용하자.
 *  i에서 X까지 가는 가장 빠른길을 찾는다.
 *  X에서 i들까지 가는 가장 빠른길들을 찾는다.
 *  어느 학생이 가장 오래걸리는지 알아보자.
 */
class Node {
  constructor(from, to, cost) {
    this.from = from;
    this.to = to;
    this.cost = cost;
  }
}
class MinHeap {
  constructor(compare) {
    this.heap = [];
    this.compare = compare;
  }
  empty() {
    if (this.heap.length == 0) return true;
    else return false;
  }
  top() {
    return this.heap[0];
  }
  push(from, to, cost) {
    let node = new Node(from, to, cost);
    this.heap.push(node);

    let curIdx = this.heap.length - 1;
    let curItem = this.heap[curIdx];
    while (curIdx > 0) {
      let parentIdx = Math.floor((curIdx - 1) / 2);
      let parentItem = this.heap[parentIdx];

      if (this.compare(parentItem.cost, curItem.cost)) break;

      this.heap[curIdx] = parentItem;
      curIdx = parentIdx;
    }
    this.heap[curIdx] = curItem;
  }
  pop() {
    let lastIdx = this.heap.length - 1;
    this.heap[0] = this.heap[lastIdx];
    this.heap.pop();

    if (this.heap.length >= 1) {
      let curIdx = 0;
      let curItem = this.heap[curIdx];
      while (curIdx < this.heap.length) {

        let leftIdx = curIdx * 2 + 1;
        let rightIdx = curIdx * 2 + 2;

        if (leftIdx >= this.heap.length) break;
        let leftItem = this.heap[leftIdx];
        let rightItem = rightIdx < this.heap.length
          ? this.heap[rightIdx]
          : null;

        let nextIdx = rightItem !== null && this.compare(rightItem.cost, leftItem.cost)
          ? rightIdx
          : leftIdx
        let nextItem = this.heap[nextIdx];

        if (this.compare(curItem.cost, nextItem.cost)) break;

        this.heap[curIdx] = nextItem;
        curIdx = nextIdx;
      }
      this.heap[curIdx] = curItem;
    }
  }
}
function main() {
  const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
  const [N, M, X] = input[0].trim().split(' ').map(Number);

  let graph = new Array(N + 1).fill(null).map(_ => []); // 1번부터 N번 까지.
  for (let i = 1; i <= M; i++) {
    let [start, to, cost] = input[i].trim().split(' ').map(Number);
    graph[start].push({
      to: to,
      cost: cost,
    })
  }

  // 최단거리 저장 배열. d[i][j] : i에서 j로 가는 최단거리.
  let d = new Array(N + 1).fill(null).map(_ => new Array(N + 1).fill(Infinity));
  for (let i = 1; i <= N; i++) {
    sol(i, graph, d);
  }
  
  let max = 0;
  for(let i=1; i<=N; i++) {
    if(i!==X) {
      let dist = d[i][X] + d[X][i];
      if(dist > max)
        max = dist;
    }    
  }
  return console.log(max);
}
function sol(start, graph, d) {
  let MH = new MinHeap((a, b) => a < b);
  for (let i = 0; i < graph[start].length; i++) {
    let [from, to, cost] = [start, graph[start][i].to, graph[start][i].cost];
    MH.push(from, to, cost);
  }

  while (!MH.empty()) {
    let cur = MH.top();
    MH.pop();
    let curNode = cur.to; // 지금 도착지.
    let curCost = cur.cost; // 지금 도착지 까지 비용.
    if (curCost < d[start][curNode]) { // curNode까지 비용이 원래 알던거 보다 더 적게 나왔다면.
      d[start][curNode] = curCost;
      for (let i = 0; i < graph[curNode].length; i++) {  // 지금 도착지와 연결된 노드들을 살펴본다.
        let [from, to, cost] = [curNode, graph[curNode][i].to, graph[curNode][i].cost];
        let nextCost = curCost + cost;
        if (nextCost < d[start][to]) {
          MH.push(from, to, nextCost);
        }
      }
    }
  }
}
main();

 

특이사항

 최대, 최소 힙을 구현하는 방법을 바꾸어보았다. 이전에 사용하던 방법보다 좀 더 직관적으로 알아볼 수 있고 MinHeap과 MaxHeap을 구현할 때 compare 함수만 a<b 에서 a>b로 바꿔주면 되어서 더 편리하다.