프로그래머스 섬연결하기

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

프로그래머스

문제 설명

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

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

 

 

최소신장트리

• 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것
• 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리
• 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음
• N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1

 

크루스칼 알고리즘

• 간선 위주의 알고리즘
• 시작점을 따로 정하지 않고 최소 비용의 간선을 차례로 대입 하면서 트리를 구성하기 때문에 사이클이 이루어지는 항상 확인 해야한다.
• 크루스칼은 간선을 기준으로 정렬하는 과정이 오래 걸린다.
• 그래프 내에 적은 숫자의 간선만을 가지는 ‘희소 그래프(Sparse Graph)’의 경우 Kruskal 알고리즘이 적합, Kruskal 알고리즘의 시간 복잡도는 O(elog₂e)
• 탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

1. 최소 비용의 간선으로 구성됨
2. 사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 한다.

 

알고리즘 

1. 초기화 및 부모 배열 설정:
   • 각 노드를 독립된 집합으로 초기화합니다. 이는 d[i] = i;를 통해 각 노드의 부모를 자기 자신으로 설정하는 작업입니다.
   • 이 과정은 유니온-파인드 알고리즘에서 집합을 관리하기 위해 사용됩니다.

   for(int i = 0; i < n; i++){ 
   	d[i] = i; 
   }

    
2. 간선 비용 기준으로 정렬:
   • 모든 간선(costs)을 비용 기준으로 오름차순으로 정렬합니다. 간선은 {출발 노드, 도착 노드, 비용}의 형식으로 저장되어 있으며, 세 번째 값인 비용을 기준으로 정렬됩니다.
   • 가장 비용이 적은 간선부터 차례로 처리하기 위함입니다.

   sort(costs.begin(), costs.end(), compare);

    
3. 간선 처리 및 트리 병합:
   • 정렬된 간선 목록을 하나씩 순차적으로 확인하면서, 두 노드가 이미 연결되어 있는지(즉, 같은 부모를 가지고 있는지) 확인합니다.
   • getParent 함수를 사용하여 각 노드의 부모를 찾습니다. 이 과정에서 경로 압축(Path Compression) 기법을 사용하여 트리의 높이를 줄입니다.

   int start = getParent(costs[i][0]);
   int end = getParent(costs[i][1]);

4. 사이클 확인 및 간선 선택:
   • 만약 두 노드가 이미 같은 집합에 속해 있지 않다면(부모가 다르다면), 두 노드를 연결하여 트리를 병합합니다. 이는 d[end] = start;로 구현되어 있으며, end 노드의 부모를 start 노드로 설정합니다.
   • 이때, 선택된 간선의 비용을 answer 변수에 더합니다. 선택된 간선은 최소 스패닝 트리에 포함됩니다.

   if (start != end) {
       d[end] = start; // 트리 병합
       answer += cost; // 비용 추가
   }

5. 최종 결과 반환:
   • 모든 간선을 처리한 후 최소 스패닝 트리를 구성하는 간선들의 비용을 반환합니다.
   • 이 비용은 모든 섬을 최소 비용으로 연결하는데 필요한 비용입니다.
    
6. 각 노드에 대해 부모를 자기 자신으로 초기화: 각 노드를 별도의 집합으로 설정.
7. 간선 비용을 오름차순으로 정렬: 비용이 가장 적은 간선부터 탐색.
8. 각 간선에 대해 부모 노드를 확인: 유니온-파인드를 사용해 부모를 찾음.
9. 사이클이 발생하지 않는 경우 간선 선택: 부모가 다르면 트리 병합, 비용 추가.
10. 모든 간선이 처리되면 총 비용 반환: MST가 완성된 후 최소 비용 반환.

 

 

동작원리

1. 모든 간선들의 가중치를 오름차 순으로 정렬
2. 가중치가 가장 작은 간선을 선택
3. 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다.
4. 이 과정을 반복

 

 

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int d[101];

int getParent(int node){
    if(node == d[node]){
        return node;
    }
    else return d[node] = getParent(d[node]);
}

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++){
        d[i] = i;
    }
    sort(costs.begin(), costs.end(), compare);
    for(int i=0; i<costs.size(); i++){
        int start = getParent(costs[i][0]);
        int end = getParent(costs[i][1]);
        int cost = costs[i][2];

        if(start != end){
            d[end] = start;

            answer += cost;
        }
    }


    return answer;
}