[JS] 등산코스 정하기

푸는데 꽤나 애를 먹었던 문제였다. 

 

문제 푸는 방법 자체는 접근을 잘했었다.

 

 

1. 문제는 코스를 왔다갔다 하는것이지만 사실 게이트 -> 봉우리까지만 체크를 하면된다.

2. 다익스트라 알고리즘을 활용해서 가중치의 합계가 아닌, 가중치가 가장 적게 나오는 값을 체크해주면 된다.

3. 만약 새 노드로 들어갔는데 내가 들어간 노드의 가중치보다 노드에서 뻗어나가는 가중치가 많다면 뻗어나가는 가중치를 사용해야 한다.

 

3으로 Node에 들어갔는데 해당 Node에 나가는 길의 가중치가 4,5만 있다면 각 길의 가중치는 4,5가 된다.

 

4. 각 게이트는 들어갈 수 없는 Node로 설정한다.

5. 산봉오리는 들어가면 나갈 수 없는 Node로 설정한다.

6. 다익스트라 알고리즘이기 때문에 최소 Heap을 활용한 우선순위큐를 구현하여 사용한다.

 

 

그런데 위처럼 프로그램을 짰더니 시간초과가 발생했다. 

 

 

 

처음에 나는 모든 Gate를 시작으로 하여 dp맵을 다 그려주었다. 그런데 생각해볼점이 있었다.

 

1. 각 Gate는 어차피 서로 간섭할 수 없다는 점

2. 정답에 출발하는 Gate의 정보가 있는것이 아닌 도착지의 정보와 가중치의 값만 있으면 된다는 점

 

즉, 문제는 어느 게이트에서 출발했는지의 정보는 필요하지 않다. 따라서 각 목적지들의 가중치의 최소값만 있기 때문에 한 Gate를 시작으로 항상 dp를 초기화하고 그때마다 최소값을 추출하는 것이 아닌, dp를 쌓아가며 맵을 그려도 괜찮다.

 

이 방식으로 dp를 만들면 어느 게이트에서 시작한 최소치인지는 알 수 없지만 각 봉우리에 도달하였을때의 최소 가중치를 얻어낼 수 있다.

 

 

 

 

 

 

 

 

class Heap {
  constructor() {
    this.heap = [0];
    this.length = 0;
  }

  getMax() {
    return this.heap[1] ? this.heap[1] : undefined;
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  push(value) {
    this.heap.push(value);
    this.length += 1;
    let idx = this.length;
    while (idx > 1) {
      const parentIdx = ~~(idx / 2);
      if (this.heap[parentIdx] >= this.heap[idx]) {
        this.swap(parentIdx, idx);
        idx = parentIdx;
      } else break;
    }
  }

  pop() {
    if (!this.length) return undefined;
    if (this.length === 1) {
      this.length--;
      return this.heap.pop();
    }
    const max = this.heap[1];

    this.heap[1] = this.heap.pop();
    this.length--;
    let idx = 1;

    while (idx < this.length) {
      const [leftIdx, rightIdx] = [idx * 2, idx * 2 + 1];

      let minIdx = 1;
      if (leftIdx > this.length) break;
      else if (rightIdx > this.length) minIdx = leftIdx;
      else
        minIdx = this.heap[leftIdx] <= this.heap[rightIdx] ? leftIdx : rightIdx;

      if (this.heap[idx] > this.heap[minIdx]) {
        this.swap(idx, minIdx);
        idx = minIdx;
      } else break;
    }
    return max;
  }
}

function solution(n, paths, gates, summits) {
    const graph = [...Array(n + 1)].map((v) => []);
    for (const [i, j, w] of paths) {
    graph[i].push([j, w]);
    graph[j].push([i, w]);
    }

    const summitMap = new Map();
    for (const summit of summits) summitMap.set(summit, true);

    const queue = new Heap();
    const dp = Array(n + 1).fill(Infinity);
    
    for (const gate of gates) {
        queue.push(gate);
        dp[gate] = 0;
      }

    
    while (queue.length) {
      const node = queue.pop();
      const weight = dp[node]
        
      if (summitMap.get(node) || dp[node] < weight) continue
       
        for (const [nextNode, newWeight] of graph[node]) {
          const newIntensity = Math.max(weight, newWeight);
          if (newIntensity < dp[nextNode]) {
            dp[nextNode] = newIntensity;
            queue.push(nextNode);
          }
        }
    }
    
    
    let answer = [0, Infinity];
    summits.sort((a, b) => a - b);
    for (const summit of summits) {
        if (dp[summit] < answer[1]) answer = [summit, dp[summit]];
    }
  
    return answer;
}