[Programmers] 섬 연결하기

안녕하세요. 오늘은 Programmers 섬 연결하기 문제를 풀어보도록 하겠습니다.

 

해당 문제는

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

코딩테스트 연습 - 섬 연결하기

 

위 링크에서 확인하실 수 있습니다.

 

그래프의 최단 신장 거리를 구하는 문제입니다. 

Kruskal 알고리즘을 활용하여 구할 수 있습니다.

 

우선 간선 정보를 cost기준 오름차순으로 정렬을 한 뒤, 가장 비용이 적은 간선부터 추가합니다.

 

여기서 주의하실 점이 간선을 추가했는데, 사이클이 발생 즉 이미 연결된 두 노드 사이에 추가로 간선을 추가하면 안 되기 때문에, 간선을 추가하실 때마다 두 노드가 연결되었다는 것을 기록해주시면 됩니다.

 

Union Find 알고리즘과 같이 매번 부모를 통일 시켜주면서 알고리즘을 진행하시면 됩니다.

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;

typedef struct edge{
    int node1, node2, cost;
}E;
vector<E> v;
bool cmp(E& a, E& b) { return a.cost < b.cost; }
int parent[104];
int getParent(int x) {
    if(parent[x] == x) return x;
    return parent[x] = getParent(parent[x]);
}
void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if(a < b) parent[b] = a;
    else parent[a] = b;
}
int isConnected(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    return (a==b);
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    for(int i = 0; i < costs.size(); i++) v.push_back({costs[i][0], costs[i][1], costs[i][2]});
    sort(v.begin(), v.end(), cmp);
    for(int i = 0; i < n; i++) parent[i] = i;

    for(int i = 0; i < v.size(); i++) {
        if(!isConnected(v[i].node1, v[i].node2)) {
            answer += v[i].cost;
            unionParent(v[i].node1, v[i].node2);
        }
    }
    return answer;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.