[코테] JS 골목 대장 호석 - 효율성 2

문제 설명

---

코드

const fs = require('fs');
const stdin = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

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

  size() {
    return this.heap.length;
  }

  getLeftChildIndex(parentIndex) {
    return 2 * parentIndex + 1;
  }

  getRightChildIndex(parentIndex) {
    return 2 * parentIndex + 2;
  }

  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2);
  }

  swap(index1, index2) {
    const temp = this.heap[index1];
    this.heap[index1] = this.heap[index2];
    this.heap[index2] = temp;
  }

  peek() {
    if (this.heap.length === 0) {
      return null;
    }
    return this.heap[0];
  }

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

  heapifyUp() {
    let currentIndex = this.heap.length - 1;
    while (currentIndex > 0) {
      const parentIndex = this.getParentIndex(currentIndex);
      if (this.heap[parentIndex][1] > this.heap[currentIndex][1]) {
        this.swap(parentIndex, currentIndex);
        currentIndex = parentIndex;
      } else {
        break;
      }
    }
  }

  remove() {
    if (this.heap.length === 0) {
      return null;
    }
    if (this.heap.length === 1) {
      return this.heap.pop();
    }
    const removedValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown();
    return removedValue;
  }

  heapifyDown() {
    let currentIndex = 0;
    while (this.getLeftChildIndex(currentIndex) < this.heap.length) {
      const leftChildIndex = this.getLeftChildIndex(currentIndex);
      const rightChildIndex = this.getRightChildIndex(currentIndex);
      const smallerChildIndex =
        rightChildIndex < this.heap.length &&
        this.heap[rightChildIndex][1] < this.heap[leftChildIndex][1]
          ? rightChildIndex
          : leftChildIndex;
      if (this.heap[currentIndex][1] > this.heap[smallerChildIndex][1]) {
        this.swap(currentIndex, smallerChildIndex);
        currentIndex = smallerChildIndex;
      } else {
        break;
      }
    }
  }
}
// 최소 힙 구현부 

const [V, E, start, end, money] = stdin[0].split(" ").map((ele) => +ele);
const edgeInfo = stdin.slice(1).map((ele) => ele.split(" ").map((ele) => +ele));
// 입력

const adjacencyList = Array.from({ length: V + 1 }, () => []);
const costs = [];

const heap = new MinHeap();

edgeInfo.forEach(([from, to, cost]) => {
  adjacencyList[from].push([to, cost]);
  adjacencyList[to].push([from, cost]);
  costs.push(cost);
});// 간선 정보 -> 인접 리스트 저장

const dijkstra = (maximum) => {
  const dist = new Array(V + 1).fill(Infinity);
  dist[start] = 0;
  heap.insert([start, 0]);
	// 이후 힙에 해당 노드에 도달하기 까지의 최소비용을 기준으로 최소 힙을 구성

  while (heap.size() !== 0) {
    const [crntVertex, crntCost] = heap.remove();
		// 힙에 남아 있는 요소 중 우선순위가 제일 높은 요소(해당 노드까지 도달하는 최소 비용으로 업데이트 된 값) 꺼내옴

    if (dist[crntVertex] != crntCost) continue;
		// 거리에 저장되어 있는 값이 최소 비용이 아니라면 스킵

    for (let [nextVertex, nextCost] of adjacencyList[crntVertex]) {
      const totalCostToNextVertex = crntCost + nextCost;
			// 현재 노드에서 갈 수 있는 후보군 중 정점까지의 비용

      if (nextCost <= maximum && totalCostToNextVertex < dist[nextVertex]) {
				// 다음 노드 까지의 비용이 만약 가정하는 총 자금(maximum)보다 작아 감당 가능
				// && 이전 while문 순회 회차에 이미 저장되어있는 다음 노드 까지의 비용(dist[nextVertex])이 작다면
				// => dist[nextVertex] 갱신 및 힙에 다음 노드와 비용을 저장
        dist[nextVertex] = totalCostToNextVertex;
        heap.insert([nextVertex, totalCostToNextVertex]);
      }
    }
  }

  return dist[end] <= money; 
// 통행비의 최대(maximum)을 제한 했을 때 구성 가능한 원하는 목적지까지의 총 비용이
// 입력에서 주어진 예산보다 작은가 여부를 리턴
};

costs.sort((a, b) => a - b);
// 간선들이 가질 수 있는 비용들을 이진탐색하기 위한 정렬

let [lt, rt] = [0, costs.length - 1];
let answer = Infinity;

while (lt <= rt) {
  const mid = Math.floor((lt + rt) / 2);
  if (dijkstra(costs[mid])) {
    if (costs[mid] < answer) {
      answer = costs[mid];
    }
    rt = mid - 1;
  } else {
    lt = mid + 1;
  }
}

console.log(answer === Infinity ? -1 : answer);

---

문제풀이 방식

1. 다익스트라(우선순위 큐를 이용한 최소 힙을 이용함)

→ 다익스트라 알고리즘을 사용하는 데 BFS 수행(우선순위 큐를 사용해 BFS이라고 해도 될지 모르겠습니다.)을 우선순위 큐를 이용했고

→ 다익스트라 알고리즘을 사용하긴 하지만 DP 배열을 해당 목적지까지의 최소비용만을 조건으로 갱신하는 것이 아닌 지날 수 있는 간선의 최대 값을 조건

2. 이후 이분 탐색을 하는데 매개변수 탐색(parametric search)를 사용한다.

   💡 매개변수 탐색(parametric search)의 조건

   1. 특정 조건을 만족하는 최댓값/최솟값을 구하는 형식의 문제여야 한다.
      → 노드 탐색 배용이 총 예산 보다 작거나 같은 조건을 만족하는 각 골목들의 통행료들 중 최솟값
   2. 최댓값을 구하는 문제의 경우 어떤 값이 조건을 만족하면 그 값보다 작은 값은 모두 조건을 만족해야 한다.(최솟값의 경우 그 값보다 큰 값은 모두 조건을 만족해야 한다.)
      → 이것도 바이너리 서치를 하기 위한 조건으로 어떤 기점으로 거짓이 되는 구간, 참이되는 구간이 있어야 미드 값을 조절할 수 있기 때문에…
   3. 답의 범위가 이산적이거나(e.g. 정수) 허용 오차 범위가 있어야 한다.
      → 바이너리 서치를 해야하기 때문에…, ****1 ≤ 골목 별 수금액 ≤ 10^9
      조건들의 출처

   골목별 비용들의 후보값들을 다익스트라 알고리즘을 수행하는 함수의 인자로 준다.
   

---

결과

1. 시간초과 → BFS로 조건을 만족하는 모든 경우를 탐색 후 목적지에 도달하는 동안의 골목 중 최대값을 배열로 저장해 이후 최소값을 출력 → Fail
2. 메모리 초과 → shift 메소드를 사용하기 때문에 시간 초과가 나는 것일까 싶어 Queue를 직접 구현 → Fail
3. 런타임 에러 → 다른 사람의 코드를 참고해 풀이 진행 → 런타임 에러
   1. 표준 입력 방식에 따라 런타임이 난다고 해 방식을 fs가 아닌 readline으로 병경 → Fail
4. 우선순위 큐 구현 방식을 변경 → Pass…