시작하며 🙄

그리디라고 해서 풀었는데, 사실상 보자마자 최소 신장 트리다! 해서 풀었어요.
뭔가 낚인 거 같아서 순간 우씨, 했는데 생각해보니 신장트리도 어떻게 보면 그리디가 맞다는 걸 느꼈습니다.

결국
1. 가장 우선적인 것부터 선택해서, 연결되어있는지를 체크해서
2. 연결되지 않았으면 연결시켜주는 거니 말이죠.

역시 생각의 틀에 갇힌다면, 사고 역시 좁혀진다는 걸 느낄 수 있던 하루였어요.
한 편으로는 6개월 전에 풀던 알고리즘을 다시 구현할 수 있었다는 것에 놀랐던 하루기도 하고. 귀했습니다. 😏

풀이 과정 📃

풀이과정이 필요할까...?! 싶었는데 혹시나 아직 신장트리가 어색한 분들을 위해, 남겨요!

1. 결국 최적의 해를 구하기 위해서 단순히 생각하자. 두 선을 잇는 데 가장 작은 선들로만 이어주면 그것이 최소 비용이 아닐까?
2. 이를 위해 먼저 우선순위 큐를 하나 만든다. 다 넣고 하나씩 빼주자.
   이는 실제로 정렬을 돌린 다음 순회를 해도 좋다! (옛날에는 이랬던 거 같은데...)
3. 결국 하나씩 빼면서 이어져 있는지를 비교해야 한다. 어떤 이어짐을 탐색해주는 배열을 하나 만들어준다.
4. 이 배열에서는 자신의 인덱스 값을 값으로 담는다. 만약 from과 to 값이 이어졌다면 재귀를 통해 이어진 그래프의 맨 위를 찾는다.
5. 만약 두 값들이 속한 그래프의 루트 인덱스를 찾았는데 서로 다르면 합해주는 과정을 수행한다. 이는 부모의 인덱스만 더 작은 인덱스 값을 가진 부모에게 묶어준다.
6. 두 그래프를 묶어줬다면 최소 비용에 현재 값을 더한다. 아니면 그냥 패스한다.
7. 이를 한 바퀴 다 순회한 후 결과값을 반환한다.

class MinHeap {
    constructor(heap = [ null ]) {
        this.heap = heap;
    }
    swap(a, b) {
        [this.heap[b], this.heap[a]] = [this.heap[a], this.heap[b]];
    }
    updateParentIndex(nowIndex) {
        return Math.floor(nowIndex / 2);
    }
    updateIndices(index) {
        return [index, index * 2, index * 2 + 1]
    }
    heappush(value) {
        this.heap.push(value);
        let nowIndex = this.heap.length - 1;
        let parentIndex = this.updateParentIndex(nowIndex);
        while(nowIndex > 1 && this.heap[nowIndex][0] < this.heap[parentIndex][0]) {
            this.swap(parentIndex, nowIndex);
            nowIndex = parentIndex;
            parentIndex = this.updateParentIndex(nowIndex);
        }
    }
    heappop() {
        if (this.heap.length === 1) return;
        if (this.heap.length === 2) return this.heap.pop();
        const min = this.heap[1];
        this.heap[1] = this.heap.pop();
        let [ nowIndex, leftIndex, rightIndex ] = this.updateIndices(1);
        if (!this.heap[leftIndex]) return min;
        if (!this.heap[rightIndex]) {
            if (this.heap[leftIndex][0] < this.heap[nowIndex][0]) {
                this.swap(nowIndex, leftIndex);
            }
            return min;
        };
        while(true) {
            if(!(this.heap[leftIndex][0] < this.heap[nowIndex][0] || this.heap[rightIndex][0] < this.heap[nowIndex][0])) break;
            const minIndex = (this.heap[leftIndex][0] < this.heap[rightIndex][0]) ? leftIndex : rightIndex;
            this.swap(nowIndex, minIndex);
            [ nowIndex, leftIndex, rightIndex ] = this.updateIndices(minIndex);
            if (rightIndex >= this.heap.length) break; 
        };
        return min;
    };
};

const findParent = (parent, x) => {
    if (parent[x] === x) return x;
    return findParent(parent, parent[x]);
}

const updateParent = (parent, a, b) => {
    const parentA = findParent(parent, a);
    const parentB = findParent(parent, b);
    if (parentA < parentB) parent[parentB] = parent[parentA];
    else if (parentB < parentA) parent[parentA] = parent[parentB];
}


const solution = (n, costs) => {
    const minHeap = new MinHeap();
    costs.map(([a, b, c]) => minHeap.heappush([c, b, a])) // [cost, from, to]
    const parent = Array.from(new Array(n), (_, idx) => idx);
    let totalMinCost = 0;
    while (minHeap.heap.length !== 1) {
        const [ cost, from, to ] = minHeap.heappop();
        if (findParent(parent, from) !== findParent(parent, to)) {
            totalMinCost += cost;
            updateParent(parent, from, to);
        }
    }
    return totalMinCost
}

무난무난.

마치며 🖐🏻

결국 역시 많이 풀면서 느낌을 파악하는 것도 중요한 듯합니다!
그리고 항상 그 답이 정답이 아닐 수도 있기에, 생각의 유연성을 가지면서 나아가야겠습니다. 이상!