[C++/PGS] Lv.3 : 섬 연결하기 (그리디 Greedy)

 

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

 

프로그래머스 그리디 - 섬 연결하기 문제

 

원래는 각 트리의 최상단 부모값을 재귀적으로 찾는 게 정석 풀이인데,

나는 복잡해서 그냥 인덱스 배열에 최소 부모값만 저장해놓고 반복문으로 갱신했다.

 

1. 최소 신장 트리를 만들기 위해, Greedy로 최솟값 간선부터 찾는 게 포인트!

2. 각 트리의 최소 부모값을 비교해서, 같으면 한 트리 내부에 있는 것으로 보고, 다르다면 두 트리를 이어줌.

 

 

나의 풀이

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int indexParent[101] = {0,};
int n;

bool cmp(vector<int> a, vector<int> b){
    return a[2] < b[2];
}

void unionNodes(int start, int end){
    int big; int small;
    if(indexParent[start] < indexParent[end]){
        big = indexParent[end];
        small = indexParent[start];
    }
    else{
        small = indexParent[end];
        big = indexParent[start];
    }
    for(int i=0; i<n; ++i){
        if(indexParent[i]==big) indexParent[i] = small;
    }
    return;
}

int solution(int N, vector<vector<int>> costs) {
    n = N;
    int answer = 0;
    int size = costs.size();
    sort(costs.begin(), costs.end(), cmp);
    for(int i=0; i<n; ++i) indexParent[i] = i;
    
    for(auto cost: costs){
        int startNode = cost[0];
        int endNode = cost[1];
        int bridge = cost[2];
        if(indexParent[startNode] != indexParent[endNode]){ // 최소 부모값이 다르면
            unionNodes(startNode, endNode); // 트리 합치기, 부모값 갱신
            answer += bridge;
        }
        
        bool isEnd = true;
        for(int i=0; i<n-1; ++i){
            if(indexParent[i] != indexParent[i+1]) {
                isEnd = false;
                break;
            }
        }
        if(isEnd) break;
    }
    
    return answer;
}