[Javascript] 프로그래머스 - 섬 연결하기

문제 설명

n개의 섬 사이에 다리를 건설하는 비용이 주어질 때, 모든 섬이 서로 통행 가능하도록 만드는 최소 비용을 구해야 합니다. 섬들은 직접 연결되지 않아도, 중간 섬을 통해 도달할 수 있으면 통행 가능한 것으로 간주합니다.

제한 사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs[i]는 세 개의 정수로 구성되며, 두 섬을 연결하는 데 필요한 비용을 의미합니다.
• 같은 연결은 중복되어 주어지지 않으며, 모든 섬이 연결될 수 있는 입력만 주어집니다.

해결 방법

알고리즘: 프림 알고리즘 (Prim's Algorithm)

• 프림 알고리즘은 하나의 정점에서 시작해 방문하지 않은 정점 중 가장 비용이 적은 간선을 선택해 최소 신장 트리를 구성하는 방식입니다.
• 우선 각 섬들을 노드로 보고, 주어진 비용 정보를 바탕으로 인접 리스트 형태의 그래프를 만듭니다. 이후 최소 힙을 활용하여, 현재 연결된 노드들에서 인접한 노드들 중 가장 비용이 적은 간선을 선택하며 전체 섬을 연결합니다.
• 방문 여부를 기록하여 이미 연결된 섬은 다시 처리하지 않으며, 모든 섬이 연결될 때까지 반복합니다.

시간 복잡도

E는 간선의 수이며, 최소 힙을 사용하여 간선을 선택하는 데 log E의 시간이 소요되므로 전체 시간 복잡도는 E log E입니다.

구현 코드

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

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

    let i = this.heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.heap[i].value >= this.heap[p].value) break;
      [this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]];
      i = p;
    }
  }

  pop() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const top = this.heap[0];
    this.heap[0] = this.heap.pop();

    const n = this.heap.length;
    let i = 0;
    while (true) {
      const l = i * 2 + 1;
      const r = i * 2 + 2;
      let min = i;

      if (l < n && this.heap[min].value > this.heap[l].value) min = l;
      if (r < n && this.heap[min].value > this.heap[r].value) min = r;
      if (min === i) break;

      [this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
      i = min;
    }

    return top;
  }

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

function solution(n, costs) {
  let answer = 0;
  const pq = new minHeap();
  const visited = new Array(n).fill(false);
  const graph = Array.from({ length: n }, () => []);

  for (const [a, b, cost] of costs) {
    graph[a].push({ node: b, value: cost });
    graph[b].push({ node: a, value: cost });
  }

  pq.push({ node: 0, value: 0 });

  while (pq.heap.length > 0) {
    const { node, value } = pq.pop();
    if (visited[node]) continue;
    visited[node] = true;
    answer += value;

    for (const next of graph[node]) {
      if (!visited[next.node]) {
        pq.push(next);
      }
    }
  }

  return answer;
}