[프로그래머스/Level 3/C++/탐욕법] 섬 연결하기

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

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

- n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

- 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

 

[문제 조건]

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

[문제 풀이]

전형적인 최소 신장 트리(MST , Minimum Spanning Tree)를 구하는 문제였다. 

 

이 문제는 대표적으로 2개의 알고리즘 (프림, 크루스칼)을 이용해 문제 해결이 가능하다.

 

필자는 크루스칼 알고리즘을 이용하여 문제를 풀었다.

 

일단, 크루스칼 알고리즘이 무엇이냐?

 

크루스칼 알고리즘은 최소 신장 트리를 구하는 알고리즘이다.

 

그럼 최소 신장 트리는 무엇인가?

 

신장 트리(Spanning Tree)

- 방향이 없는 그래프 G에서 E에 속한 간선들로 사이클을 포함하지 않으면서 모든 정점 V를 연결한 부분 그래프를 신장 트리(Spanning Tree)라 한다.

- 그래프에서 신장 트리는 여러 형태로 존재할 수 있으며, 신장 트리의 특징은 n개의 정점을 갖는 그래프에서 신장 트리에 속하는 간선의 수는 n-1개이며 "사이클을 이루지 않는다"는 특징이 있다.

- 최소신장트리(MST)란 , 무방향 그래프의 간선들에 가중치가 주어진 경우, 여러 신장 트리 중에 간선들의 가중치 합이 최소인 신장 트리를 말한다.

 

 

크루스칼 알고리즘 (Kruskal)

- 크루스칼 알고리즘은 간선들을 가중치에 따라 오름차순으로 정렬하고, 간선들을 모든 정점이 연결될때까지 선택하여 연결한다.

- 이때, 간선을 선택했을 때 사이클이 생기는지에 대한 여부는, Union-find 알고리즘을 이용하여 알아낼 수 있다.

• 간선들을 가중치에 따라 오름차순으로 정렬
• 간선들을 순서대로 선택
• 간선을 이루는 두 정점이 같은 집합(즉, 이미 두 정점 모두 신장트리에 포함됨)일 경우는 그 간선을 선택하지 않고, 다를 경우 두 정점을 union 시켜서 같은 집합으로 만든다.
• 위 과정을 모든 정점들이 같은 집합에 속할때 까지 반복

 

[소스 코드]

#include <algorithm>
#include <string>
#include <iostream>
#include <vector>

using namespace std;

vector<int> group;

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

int find(int num)
{
    if(group[num] == num) return num;
    else return group[num] = find(group[num]);
}

void merge(int a, int b)
{
    a = find(a);
    b = find(b);
    
    group[b] = a;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    int max_num = 0;
    sort(costs.begin(), costs.end(), cmp);
    for(int i=0; i<costs.size(); i++) max_num = max(max_num, max(costs[i][0],costs[i][1]));
    
    group.resize(max_num+1);
    for(int i=0; i<max_num+1; i++) group[i] = i;
    
    for(int i=0; i<costs.size(); i++)
    {
        int num1 = costs[i][0]; int num2 = costs[i][1];
        int cost = costs[i][2];
        
        if(find(num1) != find(num2))
        {
            answer += cost;
            merge(num1,num2);
        }
        else continue;
    }
    
    return answer;
}

크루스칼은 간선의 갯수가 적은 희소그래프에서는 매우 유용할 것 같지만, 간선의 개수가 많다면 프림이 더 유리할 수 있다. 프림 알고리즘은 나중에 기회가 되면 작성하도록 하겠다.

굳