문제 개요

문제: 주간 미팅

분류: 그래프 이론, 다익스트라, 최단 경로

난이도: 골드4

문제 풀이

다익스트라 알고리즘을 통해 풀 수 있었다.

KIST부터 각 장소까지의 최단 거리 배열과 씨알푸드부터 각 장소까지의 최단 거리 배열을 구한다.

한 사람의 거리 d는 (집-KIST의 최단 거리) + (집-씨알푸드의 최단 거리)라고 했으므로 앞서 구한 최단 거리 배열을 참조하여 모든 d의 합을 구하고 출력한다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let [NVE, AB, homeInfo, ...roadInfo] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

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

  empty() {
    return this.heap.length === 0;
  }

  peek() {
    return this.heap[0];
  }

  push(data) {
    this.heap.push(data);

    let i = this.heap.length - 1;
    while (i > 0) {
      const parent = ~~((i - 1) / 2);
      if (this.heap[parent].l <= this.heap[i].l) break;
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }

  pop() {
    if (this.empty()) return;

    const value = this.peek();
    [this.heap[0], this.heap[this.heap.length - 1]] = [
      this.heap[this.heap.length - 1],
      this.heap[0],
    ];

    this.heap.pop();
    this._heapify();
    return value;
  }

  _heapify() {
    const x = this.peek() ? this.peek().l : 0;
    const n = this.heap.length;
    let curr = 0;

    while (2 * curr + 1 < n) {
      const leftChild = 2 * curr + 1;
      const rightChild = leftChild + 1;
      const smallerChild =
        rightChild < n && this.heap[rightChild].l < this.heap[leftChild].l
          ? rightChild
          : leftChild;

      if (x > this.heap[smallerChild].l) {
        [this.heap[curr], this.heap[smallerChild]] = [
          this.heap[smallerChild],
          this.heap[curr],
        ];
        curr = smallerChild;
      } else break;
    }
  }
}

const dijkstra = (start, graph) => {
  const dist = new Array(graph.length).fill(Infinity);
  const pq = new PriorityQueue();

  pq.push({ v: start, l: 0 });
  dist[start] = 0;

  while (!pq.empty()) {
    let node = pq.peek().v;
    let d = -pq.peek().l;
    pq.pop();

    if (dist[node] < d) continue;

    for (let i = 0; i < graph[node].length; i++) {
      let next = graph[node][i].v;
      let cost = graph[node][i].l;
      let new_cost = d + cost;

      if (new_cost < dist[next]) {
        dist[next] = new_cost;
        pq.push({ v: next, l: -new_cost });
      }
    }
  }

  return dist;
};

const solution = (NVE, AB, homeInfo, roadInfo) => {
  const [N, V, E] = NVE.split(" ").map(Number);
  // A: KIST의 위치, B: 씨알푸드의 위치
  const [A, B] = AB.split(" ").map(Number);
  // homeInfo: 각 팀원의 집 위치가 저장된 배열
  homeInfo = homeInfo.split(" ").map(Number);
  // roadInfo: 도로 정보(도로의 양 끝 장소 a, b와 길이 l)가 저장된 배열
  roadInfo = roadInfo.map((info) => info.split(" ").map(Number));

  let graph = Array.from({ length: V + 1 }, () => []);

  // 도로를 연결하여 그래프를 생성한다.
  roadInfo.forEach(([from, to, l]) => {
    graph[from].push({ v: to, l });
    graph[to].push({ v: from, l });
  });

  // KIST와 씨알푸드에서 각 장소까지의 최단거리를 구한다.
  let KistDist = dijkstra(A, graph);
  let CrfoodDist = dijkstra(B, graph);

  let answer = 0;
  for (let i = 0; i < N; i++) {
    // 한 사람의 거리 = (집-KIST의 최단 거리) + (집-씨알푸드의 최단 거리)
    // 도달할 수 없는 경우 -1을 더한다.
    answer += KistDist[homeInfo[i]] === Infinity ? -1 : KistDist[homeInfo[i]];
    answer +=
      CrfoodDist[homeInfo[i]] === Infinity ? -1 : CrfoodDist[homeInfo[i]];
  }

  console.log(answer);
};

solution(NVE, AB, homeInfo, roadInfo);