Node.js) 백준 9370번: 미확인 도착지

https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

바로 전에 풀었던 백준 1504번: 특정한 최단경로랑 똑같은 문제입니다. 

 

문제를 설명하는 방식이 낯설었지만 재밌었습니다.   

 

시작점 S랑 경유지 G와 경유지 H가 주어집니다. 그리고 목적지 후보가 될 수 있는 지점 E 가 주어집니다. 

 

예술가가 S에서 시작해서 어떤 목적지로 최단경로로 이동합니다. 

이때 예술가를 추적하는 요원이 예술가가 G랑 H를 통과했다는 것을 알고 있습니다.

예술가는 항상 어떤 목적지를 향해 최단경로로 이동한다고 할 때.

요원이 그 목적지 후보가 될 수 있는 곳들을 알아내는 문제입니다. 

 

예술가가 S에서 시작하고 목적지 후보가 X Y Z  로 주어졌을 때. 

S에서 X로 가는 최단경로의 비용이 

S에서 G를 거쳐 H를 지나 X로 가는 최소비용과 같거나 혹은! S에서 H를 거쳐 G를 지나 X로 가는 비용과 같다면

X Y Z 중에서 X는 목적지 후보가 될 수 있습니다. 마찬가지로 비용을 계산해서 같다면 그곳은 목적지 후보가 될 수 있습니다. 

 

 

///input을 감당하기 위한 큐 작성
class Node {
  constructor(item) {
    this.item = item;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(item) {
    const node = new Node(item)
    if (this.head === null) {
      this.head = node;
    } else {
      this.tail.next = node;
    }

    this.tail = node;
    this.length += 1;
  }

  pop() {
    const popItem = this.head.item;
    this.head = this.head.next;
    this.length -= 1;
    return popItem;
  }
}

//다익스트라 알고리즘을 위한 최소힙 작성 
class MinHeap {
  constructor() {
    this.heap = [];
  }

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

  swap(arr, x, y) {
    let temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
    return;
  }


  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  bubbleUp() {
    let currentIndex = this.heap.length - 1;

    while (currentIndex > 0) {
      const parentIndex = Math.floor((currentIndex - 1) / 2);
      if (this.heap[parentIndex].cost <= this.heap[currentIndex].cost) break;
      this.swap(this.heap, parentIndex, currentIndex)
      currentIndex = parentIndex;
    }
  }


  extractMin() {
    if (this.heap.length == 1) {
      return this.heap.pop();
    }
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.sinkDown(0);
    return min
  }

  sinkDown(index) {
    const leftIndex = 2 * index + 1;
    const rightIndex = 2 * index + 2;
    const length = this.heap.length;
    let smallestIndex = index;

    if (leftIndex < length && this.heap[leftIndex].cost < this.heap[smallestIndex].cost) {
      smallestIndex = leftIndex;
    }
    if (rightIndex < length && this.heap[rightIndex].cost < this.heap[smallestIndex].cost) {
      smallestIndex = rightIndex;
    }
    if (smallestIndex !== index) {
      this.swap(this.heap, index, smallestIndex);
      this.sinkDown(smallestIndex)
    }
  }
}


//이번 문제의 입력을 책임져줄  readline
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = new Queue();
rl.on("line", function (line) {
  input.push(line)
}).on("close", function () {
  solve(input);
  process.exit();
});



function solve(x) {
  const answer = [];  // 최종답안이 담기는 곳. 
  const T = +x.pop(); // 테스트 케이스의 수.
  for (let i = 0; i < T; i++) { // 테스트 케이스 만큼 반복 .
    let tempAnswer = [];   // 각 테스트케이스에 대한 답이 담기는 곳. 
    const [n, m, t] = x.pop().split(' ').map(v => +v); // 첫째줄에 n은 노드 수, m은 간선수, t는 목적지 후보의 수. 
    const [s, g, h] = x.pop().split(' ').map(v => +v); //두번째 줄은 출발점s와  경유지 g,h 

    let adj = Array.from(Array(n + 1), () => []); // 인접노드를 표시가히기 위한 2차원 배열. 
    for (let j = 0; j < m; j++) {  //간선의 수만큼 반복 
      const [a, b, d] = x.pop().split(' ').map(v => +v); // 노드 a와 노드 b 사이의 거리가 d 
      adj[a].push({ node: b, dist: d });  // 방향이 없는 그래프라고 하니 노드 순서를 바꿔서 각각 넣어줌. 
      adj[b].push({ node: a, dist: d });
    }

    //**solution
    //출발점에서 목적지로 가는 최단경로가 
    //출발점에서 g,h를 거쳐서 가는 최단경로와 같거나
    //출발점에서 h,g를 거쳐서 가는 최단경로와 같으면 
    //그것은 목적지 후보가 될 수 있다. 
    const routeS = route(s, n, adj); // 출발지점에서 어떤 지점으로 가는 데 필요한 최단거리를 나타내는 배열
    const routeG = route(g, n, adj); // g지점에서 어떤 지점으로 가는 데 필요한 최단거리를 나타내는 배열
    const routeH = route(h, n, adj); // h지점에서 어떤 지점으로 가는 데 필요한 최단거리를 나타내는 배열

    for (let k = 0; k < t; k++) {
      const E = +x.pop(); // 문제에서 주어진 검사해야할 목적지. 
      const base = routeS[E]; // 출발점에서 목적지까지로 가는 최단 경로 
      const possibleA = routeS[g] + routeG[h] + routeH[E]; //출발점에서 g,h를 거쳐서 가는 최단경로
      const possibleB = routeS[h] + routeH[g] + routeG[E]; //출발점에서 h,g를 거쳐서 가는 최단경로
      if (base != Infinity && (base == possibleA || base == possibleB)) { // 갈수 있는 목적지이고 && 최단경로 값이 같다면 도착 가능한 목적지 후보가 된다. 
        tempAnswer.push(E);
      }
    }

    answer.push(tempAnswer.sort((a, b) => a - b).join(' '));
  }
  console.log(answer.join('\n'))
}



// n개의 노드, adj는 인접노드와 그 노드까지의 거리가 담겨있다. s는 출발점이다. 
// s에서 각 노드로 가는데 필요한 최소비용을 담은 배열을 반환한다. 
function route(s, n, adj) {

  let MinDist = new Array(n + 1).fill(Infinity);
  MinDist[s] = 0;

  let heap = new MinHeap();
  heap.insert({ node: s, dist: 0 });

  while (!heap.empty()) {
    let now = heap.extractMin();
    for (let i = 0; i < adj[now.node].length; i++) {
      const { node, dist } = adj[now.node][i];
      if (MinDist[node] > now.dist + dist) {
        MinDist[node] = now.dist + dist;
        heap.insert({ node: node, dist: MinDist[node] })
      }
    }
  }

  return MinDist  
}

 

답은 맞췄지만.. 다른 분들 코드를 보니까 제 코드가 부끄러워서  이 글 작성하는 것도 부끄럽습니다. 좀 더 열심히 해서 부끄럽지 않은 코드를 쓰는 사람이 돼야겠습니다.