[Programmers] (고득점KIT) Greedy - 섬 연결하기
https://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의 비용이 주어지지 않습니다.
모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
연결할 수 없는 섬은 주어지지 않습니다.
입출력 예
n | costs | return |
---|---|---|
4 | [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] | 4 |
Solution
#include <string>
#include <vector>
#include <algorithm>
#define MAX 101
using namespace std;
int Parent[MAX];
int getParent(int num){
if(num == Parent[num]) return num;
return Parent[num] = getParent(Parent[num]);
}
void unionParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(a != b) Parent[a] = b;
}
bool findParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(a == b) return true;
else return false;
}
int solution(int n, vector<vector<int>> costs) {
int answer = 0;
vector<pair<int, pair<int, int>>> vec;
for(int i = 0; i < costs.size(); i++){
int start = costs[i][0];
int end = costs[i][1];
int cost = costs[i][2];
vec.push_back({cost, {start, end}});
}
for(int i = 0 ; i < n; i++) Parent[i] = i;
sort(vec.begin(), vec.end());
for(int i = 0; i < vec.size(); i++){
int start = vec[i].second.first;
int end = vec[i].second.second;
int cost = vec[i].first;
if(!findParent(start, end)){
answer += cost;
unionParent(start, end);
}
}
return answer;
}
#include <string>
#include <vector>
#include <algorithm>
#define MAX 101
using namespace std;
int Parent[MAX];
int getParent(int num){
if(num == Parent[num]) return num;
return Parent[num] = getParent(Parent[num]);
}
void unionParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(a != b) Parent[a] = b;
}
bool findParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(a == b) return true;
else return false;
}
int solution(int n, vector<vector<int>> costs) {
int answer = 0;
vector<pair<int, pair<int, int>>> vec;
for(int i = 0; i < costs.size(); i++){
int start = costs[i][0];
int end = costs[i][1];
int cost = costs[i][2];
vec.push_back({cost, {start, end}});
}
for(int i = 0 ; i < n; i++) Parent[i] = i;
sort(vec.begin(), vec.end());
for(int i = 0; i < vec.size(); i++){
int start = vec[i].second.first;
int end = vec[i].second.second;
int cost = vec[i].first;
if(!findParent(start, end)){
answer += cost;
unionParent(start, end);
}
}
return answer;
}
크루스칼 알고리즘을 활용하는 문제다.
우선 크루스칼 알고리즘에 대해 언급하자면
- 모든 간선들의 가중치를 오름차순으로 정렬한다.
- 가중치가 가장 작은 간선을 선택한다.
- 2에서 선택한 간선이 연결하려는 2개의 노드가 아직 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다.
- 위의 과정을 반복한다.
이러한 알고리즘이다. MST를 만드는 게 이 문제의 핵심이다.
int Parent[MAX];
int getParent(int num){
if(num == Parent[num]) return num;
return Parent[num] = getParent(Parent[num]);
}
void unionParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(a != b) Parent[a] = b;
}
bool findParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(a == b) return true;
else return false;
}
Union Find 에 필요한 코드들이다. 어렵게 생각할 건 없고 Parent 배열을 처음에는 모든 노드에 대해 자신으로 초기화 시켜둔다(Solution 함수에서 자세히 나온다.).
그리고 이 세가지 함수를 토대로 크루스칼 알고리즘을 구현하면 된다. 코드 자체는 어렵지 않다. Union Find 기법을 쓰기 위해 반드시 숙지해야하는 세 함수니까 외우다시피 알고있는 게 좋다. (Index tree 같은 기법을 쓰기위해서도 필요하다. )
다시 Solution 함수를 보자.
vector<pair<int, pair<int, int>>> vec;
for(int i = 0; i < costs.size(); i++){
int start = costs[i][0];
int end = costs[i][1];
int cost = costs[i][2];
vec.push_back({cost, {start, end}});
}
for(int i = 0 ; i < n; i++) Parent[i] = i;
sort(vec.begin(), vec.end());
각 데이터간에 단방향 그래프는 아니지만 현재로써는 직접 탐색하는것도 아니고 그 경로에 대한 정보만 있으면 되니까 신경쓰지말고 입력한다.
그 후 각 노드들은 모두 본인을 Parent로 보고 있도록 세팅해둔다. 또한 모든 노드들을 cost 기준으로 정렬시킨다.
for(int i = 0; i < vec.size(); i++){
int start = vec[i].second.first;
int end = vec[i].second.second;
int cost = vec[i].first;
if(!findParent(start, end)){
answer += cost;
unionParent(start, end);
}
}
return answer;
그 후 하나씩 꺼내가며 해당 경로에 두 시작점과 끝점이 같은 Parent를 공유하지 않는다면(연결되어있지 않다면) 해당 경로를 연결하고 answer에 cost를 저장한다.
어차피 오름차순 정렬이니까 최소한의 비용을 가지는 연결이 자동으로 완성된다.
MST, 크루스칼 알고리즘에 대한 개념이 있다면 풀 수 있는 문제.
Author And Source
이 문제에 관하여([Programmers] (고득점KIT) Greedy - 섬 연결하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sierra9707/Programmers-고득점KIT-Greedy-섬-연결하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)