[JS][백준]1197_최소 스패닝 트리

문제 번호

1197번: 최소 스패닝 트리

 

 

 

알고리즘 분류

• 그래프 이론
• 최소 스패닝 트리

 

문제 풀이

 유니온 파인드와 MST의 개념을 알고 있으면 쉽게 풀 수 있다.

 

문제에서 주어진 간선의 정보들을 MinHeap에 저장해준다.

  let graph = new MinHeap();
  for (let i = 1; i < input.length; i++) {
    let [start, end, cost] = input[i].split(' ').map(Number);
    graph.push(start, end, cost);
  }

 

 이제 유니온 파인드를 이용하여 사이클이 생기는지 검사하면서 간선의 가중치가 낮은 정점들부터 트리에 추가하면 된다.

 

응용 사항이 없이 MST를 만들 줄 아냐 모르냐의 문제기 때문에 자세하게 설명할 내용이 딱히 없는 것 같다.

 

전체 코드

/**
 * 유니온파인드를 사용해야한다.
 * 간선의 비용이 가장 낮은 간선부터 오름차순으로 정렬한다.
 * 비용이 가장 낮은 간선을 추가하였을때 사이클이 생기지 않는다면 해당 간선을 추가한다.
 *    사이클 검사는 유니온파인드를 이용한다.
 * 
 * 시작 정점은 어디? // 간선의 비용이 젤 작은곳.
 * 
 */

class Node {
  constructor(start, end, cost) {
    this.start = start;
    this.end = end;
    this.cost = cost;
  }
}
class MinHeap {
  constructor() {
    this.heap = [null];
  }
  length() {
    return this.heap.length - 1;
  }
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
  push(start, end, cost) {
    let node = new Node(start, end, cost);
    this.heap.push(node);

    let cur = this.length();
    let parent = Math.floor(cur / 2);

    while (cur > 1 && this.heap[parent].cost > this.heap[cur].cost) {      
        this.swap(cur, parent);
        cur = parent;
        parent = Math.floor(cur / 2);      
    }
  }
  pop() {
    let top = this.heap[1];
    if (this.length() === 1) {
      this.heap = [null];
      return top;
    }

    this.heap[1] = this.heap.pop();

    let cur = 1;
    let left = cur * 2;
    let right = cur * 2 + 1;

    if (!this.heap[left])
      return top;
    if (this.heap[left]) {
      if (!this.heap[right]) {
        if (this.heap[cur].cost > this.heap[left].cost) {
          this.swap(cur, left)
          return top;
        }
      }
    }

    while ((right <= this.length()) &&
      (this.heap[cur].cost > this.heap[left].cost || this.heap[cur].cost > this.heap[right].cost)) {
      let minIdx = this.heap[left].cost > this.heap[right].cost ? right : left;
      this.swap(cur, minIdx);
      cur = minIdx;
      left = cur * 2;
      right = cur * 2 + 1;
    }

    return top;
  }
}
function getParent(a, b, parent) {
  let A = findParent(a, parent);
  let B = findParent(b, parent);
  if (A === B) return true;
  else return false;
}
function findParent(x, parent) {
  if (parent[x] !== x) {
    return parent[x] = findParent(parent[x], parent);
  } else {
    return x;
  }
}
function unionParent(a, b, parent) {
  let A = findParent(a, parent);
  let B = findParent(b, parent);
  if (A < B) {
    parent[B] = A;
  } else {
    parent[A] = B;
  }
}
function main() {
  const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
  const [V, E] = input[0].trim().split(' ').map(Number);
  
  let graph = new MinHeap();
  for (let i = 1; i < input.length; i++) {
    let [start, end, cost] = input[i].split(' ').map(Number);
    graph.push(start, end, cost);
  }  

  let parent = new Array(V + 1).fill(0);
  parent.forEach((v, i) => { parent[i] = i });
  

  console.log(sol(V, E, graph, parent));
}
function sol(V, E, graph, parent) {
  let ans = 0;

  while (graph.length()) {
    let cur = graph.pop();
    let [start, end, cost] = [cur.start, cur.end, cur.cost];
    if (!getParent(start, end, parent)) {
      unionParent(start, end, parent);
      ans += cost;
    }
  }
  return ans;
}
main();

특이사항