[코딩테스트]백준 - 최소 스패닝 트리(feat. heap)

(힙 공부한거 응용할 겸) 최소스패닝트리 문제를 다시 풀어보았다.

문제

최소 스패닝 트리(1197)

해결한 코드

const fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let vertexsAndEdges = input[0].split(' ').map((e) => +e)
const vertexNumber = vertexsAndEdges[0]
const edgesNumber = vertexsAndEdges[1]
if (vertexNumber === 1) {
    console.log(0)
} else if (edgesNumber === 1) {
    let t = input[1].split(' ')
    console.log(t[2]/1)
} else {
    let cycleTable = Array(vertexNumber + 1)
    for (let i = 0; i <= vertexNumber; i++) {
        cycleTable[i] = i
    }

    class Heap {
        constructor() {
            this.nodes = []
            this.size = 0
        }

        insert(data) {
            this.nodes.push(data)
            this.bubbleUp()
        }

        bubbleUp(index = this.nodes.length - 1) {
            if (index < 1) return

            let current = this.nodes[index]
            let parentIndex = Math.floor((index - 1) / 2)
            let parent = this.nodes[parentIndex]

            if (current[2] >= parent[2]) return

            this.nodes[index] = parent
            this.nodes[parentIndex] = current
            index = parentIndex
            this.bubbleUp(index)
        }

        getSize() {
            return this.size
        }

        extract() {
            const min = this.nodes[0]
            if (this.nodes.length === 1) {
                this.nodes.pop()
                return min
            }
            this.nodes[0] = this.nodes.pop()
            this.trickleDown()
            return min
        }

        trickleDown(index = 0) {
            let leftChildIndex = index * 2 + 1
            let rightChildIndex = index * 2 + 2
            let minimum = index

            if (!this.nodes[leftChildIndex] && !this.nodes[rightChildIndex]) return

            if (!this.nodes[rightChildIndex]) {
                // only left 
                if (this.nodes[leftChildIndex][2] < this.nodes[minimum][2]) {
                    minimum = leftChildIndex
                }
            } else {
                // left and right 
                if (this.nodes[leftChildIndex][2] > this.nodes[rightChildIndex][2]) {
                    // left weight > right weight 
                    if (this.nodes[rightChildIndex][2] < this.nodes[minimum][2]) {
                        minimum = rightChildIndex
                    }
                } else {
                    if (this.nodes[leftChildIndex][2] < this.nodes[minimum][2]) {
                        minimum = leftChildIndex
                    }
                }
            }
            if (index !== minimum) {
                let t = this.nodes[index]
                this.nodes[index] = this.nodes[minimum]
                this.nodes[minimum] = t
                this.trickleDown(minimum)
            }
        }
    }

    let setTable = (start, end) => {
        let endValue = cycleTable[end]
        for (let i = 1; i < cycleTable.length; i++) {
            if (cycleTable[i] === endValue) cycleTable[i] = cycleTable[start]
        }
        return cycleTable
    }
/*
    let isIntegrated = (cycleTable) => {
        for (let i = 2; i < cycleTable.length; i++) {
            if (cycleTable[i - 1] !== cycleTable[i]) return false
        }
        return true
    }
*/
    let linksHeap = new Heap()
    for (let i = 1; i < input.length; i++) {
        linksHeap.insert(input[i].split(' ').map((e) => +e))
    }
    let sum = 0
    let count = 0
    // while (!isIntegrated(cycleTable))
    while (count !== vertexNumber-1){
        let [start, end, weight] = linksHeap.extract()
        if (cycleTable[start] === cycleTable[end]) continue
        if (cycleTable[start] !== cycleTable[end]) {
            cycleTable = setTable(start, end)
            count++
            sum += weight
        }
    }
    console.log(sum)
}

풀이

※ 우선 힙을 구현한다.
문제 특성상 최소 힙을 구현하였다.

1. 각 간선에 대한 정보를 배열 형태로 힙에 삽입한다.

예를 들어 [1, 2, 1] 이라면, heap = [[1, 2, 1]] 처럼 삽입한다.
삽입할 때마다 가중치가 가장 작은 배열이 부모 노드가 되도록 재정리한다.

2. Union-find로 사이클을 검사하면서 정점들을 연결한다.

• 힙에서 노드를 하나 뺀다.
• 뺀 노드의 간선 정보를 통해, 두 정점의 연결 상태를 확인한다.
• 만약 두 정점이 연결되지 않았다면 : 사이클 테이블의 값을 통일시켜 둘을 연결시킨다.
  • 가중치를 합한다.
• 만약 두 정점이 연결되었다면 : 사이클 테이블 값이 같다는 소리이다. 그냥 패스한다.

3. 모든 점들이 연결되면 끝낸다.

가중치의 합을 출력한다.

예전에 풀었던 풀이는 시간복잡도를 너무 고려않은 방법이라 새롭게 풀어봤는데..
시간이 많이 줄어들긴 했지만 다른 사람들의 풀이에 비해선 아직 부족한 듯 하다 ㅜㅜ
우선순위 큐로 구현하는게 더 좋은건지, 아니면 그냥 연결된 간선의 갯수가 정점의 갯수보다 -1일 때 반복문을 멈추는게 키포인트인지.. 고민고민

방금 그냥 연결된 간선의 갯수가 정점의 갯수보다 -1일 때 반복문을 멈추는 방식으로 돌렸더니 엄청 빨라졌다.

그래.. while문 돌리는 동안 계속 for문으로 cycleTable 돌리면서 검사하니.. 시간이 늘어날 수밖에..