최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하라
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 본다.
예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능
cost : n개의 섬 사이에 다리를 건설하는 비용
_ 섬의 개수 n : 1 이상 100 이하
_ costs의 길이 : ((n-1) * n) / 2이하
_ 임의의 i에 대해,
costs[i][0] - costs[i] [1] : 연결되는 두 섬의 번호가 들어있고,
costs[i] [2] : 다리를 건설할 때 드는 비용
_ 같은 연결은 두 번 주어지지 않음(순서가 바뀌더라도 같은 연결)
_ 모든 섬 사이의 다리 건설 비용이 주어지지 않음(이 경우, 두 섬 사이의 건설이 불가능한 것)
_ 연결할 수 없는 섬은 주어지지 않음
- Greedy알고리즘 중에서도 최장신장트리를 구하는 문제이다.
- 특히 같은 집단안에 있는지를 알아내는 Union-find를 활용하며 다음과 같은 방법으로 구현할 수 있다.
1) 배열
2) 트리
- 이중에서 배열을 통해 집단의 루트만 표현하며
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(vector<int> a, vector<int> b) {
return a[2] == b[2] ? a[0] < b[0] : a[2] < b[2];
}
int solution(int n, vector<vector<int>> costs) {
int answer = 0, arr[n];
for(int i = 0; i < n; i++) {
arr[i] = i;
}
sort(costs.begin(), costs.end(), compare);
for(int i = 0; i < costs.size(); i++) {
if(costs[i][2] == 0) continue;
if(arr[costs[i][0]] != arr[costs[i][1]]) {
for(int j = 0; j < n; j++) { //같은 루트를 가진 모든 다리의 루트를 변경
if(arr[j] == arr[costs[i][1]])
arr[j] = arr[costs[i][0]];
}
answer += costs[i][2];
}
}
return answer;
}
- 연결된 섬의 개수를 파악하여 그 뒤의 추가적인 일을 제한함.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(vector<int>& a, vector<int>& b) {
return a[2] < b[2];
}
int solution(int n, vector<vector<int>> costs) {
int answer = 0, cnt = 1, arr[n];
for(int i = 0; i < n; i++) {
arr[i] = i;
}
sort(costs.begin(), costs.end(), compare);
for(int i = 0; i < costs.size(); i++) {
if(costs[i][2] == 0 || arr[costs[i][0]] == arr[costs[i][1]]) continue;
if(arr[costs[i][0]] != arr[costs[i][1]]) {
for(int j = 0; j < n; j++) { //같은 루트를 가진 모든 다리의 루트를 변경
if(arr[j] == arr[costs[i][1]])
arr[j] = arr[costs[i][0]];
}
answer += costs[i][2];
cnt++;
}
if(cnt == n) break;
}
return answer;
}
이전 코드는 모든 섬을 연결해도 추가적으로 if문 안으로 들어가는 경우가 발생한다는 점을 알 수 있다. → arr의 내용이 하나로 통일되지 않은 경우/루트를 변경할 때 오류가 생기는지
두번째 for문 안의 if(arr[j] == arr[costs[i][1]])에서 만약 기준이되는 값이 바뀌고 다음 값도 바뀌어야할 때 다르게 적용되므로 미리 arr[costs[i][1]의 값을 따로 저장하고 비교해준다.
그리고 모든 섬을 연결했을 때 실패한 경우가 생기는 것을 보아 기대값보다 크거나 작은 최소비용에 맞지 않는 경우가 일어남을 알 수 있다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(vector<int>& a, vector<int>& b) {
return a[2] < b[2];
}
int solution(int n, vector<vector<int>> costs) {
int answer = 0, cnt = 1, arr[n];
for(int i = 0; i < n; i++) {
arr[i] = i;
}
sort(costs.begin(), costs.end(), compare);
for(int i = 0; i < costs.size(); i++) {
if(costs[i][2] == 0 || arr[costs[i][0]] == arr[costs[i][1]]) continue;
int tmp = arr[costs[i][1]];
for(int j = 0; j < n; j++) { //같은 루트를 가진 모든 다리의 루트를 변경
if(arr[j] == tmp)
arr[j] = arr[costs[i][0]];
}
answer += costs[i][2];
cnt++;
if(cnt == n) break;
}
return answer;
}