[프로그래머스 C++] 섬 연결하기

 

[프로그래머스 C++] 섬 연결하기

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

 

해결방안

 

탐욕법

최소신장트리 Minimum Spanning Tree(MST)

• 프루스칼 알고리즘 (Kruskal MST)

 

---

 

정답 코드

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int city[101];
 
struct Edge
{
    int start, end, cost;
    Edge(int a, int b, int c)
    {
        start = a;
        end = b;
        cost = c;
    }
 
    bool operator<(const Edge& c) const{
        return cost < c.cost;
    }
};
 
vector<Edge> v;
 
int Find(int x)
{
    if (x == city[x]) return x;
 
    return city[x] = Find(city[x]);
}
 
void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
 
    if (a != b)
        city[a] = b;
}
 
 
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
 
    for (int i = 0; i < n; i++){
        city[i] = i;
    }
 
    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());
 
    for (int i = 0; i < v.size(); i++)
    {
        int fa = Find(v[i].start);
        int fb = Find(v[i].end);
 
        if (fa != fb){
            answer += v[i].cost;
            Union(fa, fb);
        }
    }
 
    return answer;
}

 

---

 

수정 코드

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int city[101]; // 각 도시(노드)가 어떤 집합에 속해 있는지 표현하는 배열
 
// Find 함수는 주어진 노드 x가 어떤 집합에 속해 있는지 찾는 함수. 
// 재귀적으로 자신이 속한 집합의 대표 원소(root node)를 찾아 반환. 
// 경로 압축(Path Compression) 기법을 사용하여 해당 노드의 부모 노드를 바로 root node로 설정합니다.
int Find(int x)
{
    if (x == city[x]) return x;
 
    return city[x] = Find(city[x]);
}
 
// Union 함수는 두 개의 원소가 속한 집합을 합치는 연산입니다. 
// 각 원소가 속한 집합을 찾아서 다르다면 한 쪽의 root node를 다른 쪽으로 변경함으로써 합치게 됩니다.
void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
 
    if (a != b)
        city[a] = b;
}
 
bool Compare(vector<int> a, vector<int> b) {
    return a[2] < b[2];
}
 
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
 
    for (int i = 0; i < n; i++){
        city[i] = i;
    }
 
    sort(costs.begin(), costs.end(), Compare); // 다리건설 비용 오름차순 정렬. 간선의 가중치(costs[i][2]) 
 
    for (int i = 0; i < costs.size(); i++)
    {
        int fa = Find(costs[i][0]);
        int fb = Find(costs[i][1]);
 
        if (fa != fb){
            answer += costs[i][2];
            Union(fa, fb);
        }
    }
 
    return answer;
}

 

 

---

 

간결한 코드 - Union 함수 생략

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int city[101];
 
int Find(int x)
{
    if (x == city[x]) return x;
 
    return city[x] = Find(city[x]);
}
 
bool Compare(vector<int> a, vector<int> b) {
    return a[2] < b[2];
}
 
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
 
    for (int i = 0; i < n; i++){
        city[i] = i;
    }
 
    sort(costs.begin(), costs.end(), Compare);
 
    for (int i = 0; i < costs.size(); i++)
    {
        int start = Find(costs[i][0]);
        int end = Find(costs[i][1]);
 
        if (start != end){
            answer += costs[i][2];            
            city[end] = start; // Union 과정
        }
    }
 
    return answer;
}
 
int main()
{
    vector<vector<int>> testcase = { {0,1,1},{0,2,2},{1,2,5},{1,3,1},{2,3,8} };
    cout << solution(4, testcase);
 
    return 0;
}