[프로그래머스] 42861: 섬 연결하기, 크루스칼 vs 다익스트라 vs 플로이드

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

프로그래머스

 

크루스칼 알고리즘 코드만 작성하면 풀리는 문제이다.

 

크루스칼 알고리즘 vs 다익스트라 vs 플로이드

크루스칼 알고리즘은 그래프의 모든 노드를 최소한의 비용으로 연결하는 부분 그래프를 찾는다.

다익스트라 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이고,

플로이드-워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다.

 

사용 기법 및 방식

크루스칼 - 서로소 집합

다익스트라 - 그리디

플로이드 - DP

 

코드

#include <bits/stdc++.h>

using namespace std;
int parent[104];
vector<pair<int, pair<int, int>>> edges;

int findParent(int x){
    if(parent[x]==x) return x;
    return parent[x]=findParent(parent[x]);
}
void unionParent(int a, int b){
    a = findParent(a);
    b = findParent(b);
    if (a<b) parent[b]=a;
    else parent[a]=b;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    //1. 입력
    for(int i=1;i<=n;i++) parent[i]=i;
    for(int i=0;i<costs.size();i++){
        edges.push_back({costs[i][2], {costs[i][0], costs[i][1]}});
    }
    //2. 정렬
    sort(edges.begin(), edges.end());
    //3. 크루스칼 알고리즘 수행
    for(int i=0;i<edges.size();i++){
        int cost = edges[i].first;
        int a = edges[i].second.first;
        int b = edges[i].second.second;
        if(findParent(a) != findParent(b)){
            unionParent(a, b);
            answer += cost;
        }
    }
    
    
    return answer;
}