[프로그래머스 Lv.3 / C++] Day68. 섬 연결하기

2024. 08. 10 - 코딩테스트 스터디 Day68

 
 

01. 문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

 
 

02. 제한사항

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

 
 

03. 입출력 예

n	costs	return
4	[[0,1,1][0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

 
입출력 예 설명
costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

 
 

04. 풀이 및 답

이 문제를 해결하기 위해서는 최소 신장 트리 알고리즘을 사용해야 한다.
최소 신장 트리 알고리즘에는 크루스칼 알고리즘, 프림 알고리즘이 대표적인 알고리즘이다.
나는 크루스칼 알고리즘을 사용하여 문제를 풀어보았다.
 

💎 크루스칼 알고리즘의 동작 과정 💎

1. 간선을 가중치 기준으로 오름차순 정렬한다.
2. 간선을 순차적으로 순회하며 트리에 순환성이 생기지 않는 간선을 추가한다.
3. 최소 신장 트리가 완성될 때까지 2번 과정을 반복한다.

 

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

using namespace std;

vector<int> parent(101);

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

int findParent(int index) {
    if (parent[index] == index) return index;
    return parent[index] = findParent(parent[index]);
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
    
    sort(costs.begin(), costs.end(), cmp);
    
    for (int i = 0; i < costs.size(); i++) {
        int start = findParent(costs[i][0]);
        int end = findParent(costs[i][1]);
        int cost = costs[i][2];
        
        if (start != end) {
            answer += cost;
            parent[end] = start;
        }
    }
    
    return answer;
}

parent 배열은 각 정점의 부모 정점을 기록한다. 처음에는 모두 자기 자신을 부모 정점으로 가지도록 초기화한다.
costs 배열을 다리 건설 비용을 기준으로 오름차순 정렬한다.
 
findParent 함수를 통해 start와 end 정점에 대한 부모 정점을 찾는다. 
start와 end의 부모 정점이 다르면 이 간선의 비용을 answer에 더하고, end 정점의 부모 노드를 start로 설정한다.
 
 
1. findParent 함수 추가 설명

int findParent(int index) {
    if (parent[index] == index) return index;
    return parent[index] = findParent(parent[index]);
}

파라미터로 들어온 index 값과, 그 index의 부모 값이 같으면 index 값을 리턴하고,
같지 않다면 부모 노드를 찾아 반환해 준다. 
 
다음은 동작 예시이다.

초기 상태 가정
- parent 배열: [0, 1, 1, 3, 3]

findParent(2)가 호출되었다면,
index = 2, parent[2]는 1이므로 findParent(1)을 호출하게 된다.
findParent(1)은 1이므로 1을 리턴한다.

 
 

정답!

---

끝
 
 
참고한 게시글

[그래프 알고리즘] 크루스칼 알고리즘 Kruskal Algorithm

 

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