개요
-
문제 설명
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의 비용이 주어지지 않습니다.
모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
연결할 수 없는 섬은 주어지지 않습니다.
접근 방식
다익스트라 알고리즘 변형
-
우선 처음 봤을 때 최소의 비용으로 모든 섬을 통행가능하다고 한걸 보자마자 다익스트라 알고리즘이 떠올랐다.
다익스트라 알고리즘으로 코드를 짜고 각 노드의 최단 경로 비용이 갱신이 될 때 map을 이용해 연결된 섬들을 다 저장했다.
마지막에 map을 순회하며 비용들을 계산하는 식으로 풀었으나 틀렸다. -
그래서 아! 다른 노드에서 시작을 한다면 값이 다르겠구나라는 생각을 떠올리고,
n도 최대값이 100으로 적은 숫자라 모든 노드에서 위 방식대로 다익스트라를 한번씩 돌리고 map을 순회하며 계산한 비용 중에 최소값을 구했지만 틀렸다. -
이거저거 찾아보고 고민한 결과 이유는 다익스트라 알고리즘은 한 섬에서 출발해
다른 섬으로 가는 최단경로를 구하는 방식으로, 이 문제와는 안 맞다.이 문제에서 요구하는 부분은 각 섬에서 인근 섬까지의 최저 간선 비용만을 구해 합산하는 것으로,
각 섬에서 다른 모든 섬으로 최단경로를 구해 간선 비용을 구하는게 아니다.
-
따라서 섬에서 다른 섬으로 이동할 때, 모든 경로중 최단 경로를 구하는게 아니라
그리디 알고리즘 방식으로 각 섬에서 바로 옆섬으로 이동할 때의 최소비용의 간선만 고른 후,
이동한 섬은 다시 안 보는 식으로 구현하면 된다. -
이를 위해선 다익스트라알고리즘을 변형을 좀 해야한다.
visited[curNode.second]=true; for(auto elem : adj[curNode.second]) { if(visited[elem.first]) continue; //각섬에 저장되어야하는 노드는 시작노드에서 시작해서 해당 노드로 갈때 //각섬에서 근처 섬으로 최소비용의 다리로만 갈수 있도록 해야함 //이렇게 하기위해서 모든 섬은 다리중에서 최소비용으로 짓고, 방문을 한 섬은 다시 방문x if(shortest[elem.first] > elem.second) { shortest[elem.first]=elem.second; pq.push({ elem.second,elem.first }); } }priority_queue에서 뽑은 top값의 주위 섬을 순회하며, 이미 방문한 섬이면 바로 pass한다.
방문 안 한 주위 섬중에 해당 섬으로 가는 간선이 줄어들 수 있다면 갱신한다.원래 다익스트라 방식이면 방문한 섬이라도 현재 노드를 통해 방문했을 시,
cost가 더 줄어들 수 있다면 갱신을 해줬는 데,
이제는 각 섬에서 다른 섬으로 최소비용의 간선만 택하고 이미 방문한 섬은 쳐다보지도 않는다. -
이렇게 실행하면 shortest배열의 각 index에 저장된 값은
이전 index 섬에서 해당 index의 섬으로 연결된 간선의 최소비용이다.
모든 노드에서 visited배열에 true체크되어있는 노드를 체크한다.
shortest배열의 인덱스가 해당 노드인 값을 조사해 최저 간선비용들을 구하면 된다.
하지만, 이 방식도 결국 시작노드를 어디서부터 하냐에 따라 차이가 나게 되므로
시작노드에 반복문을 통해 모든 노드를 넣고 실행한 후 최소값을 추출해야한다.
크루스칼 알고리즘
크루스칼 알고리즘은 최소 스패닝 트리를 만드는 알고리즘이다.
간선을 정렬 후 최소값의 간선부터 컴퍼넌트로 연결한다는 점에서 그리디 알고리즘을 따른다.
최소 스패닝 트리는 간선마다 가중치가 있는 트리에서, 가중치의 합이 최소가 되는 트리이다.
크루스칼 알고리즘의 방식은
-
간선을 오름차순으로 우선 정렬한다.
-
해당 간선의 두 정점이 이미 연결된 컴퍼넌트 내부에 있다면 패스하고,
두 정점이 연결이 안 되어 있다면 연결해준다. -
간선을 정점-1개 뽑으면 끝난다.
여기서 두 노드가 같은 컴퍼넌트 내부에 있는지 확인하기 위해 유니온 파인드가 사용된다.
유니온 파인드
유니온 파인드는 각 노드의 부모노드를 저장하는 벡터를 가지고 있는 자료구조다.
find함수와 merge함수로 이뤄져있다.
내부 배열을 -1값으로 초기화하고
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; ++i)
parent[i] = -1;
}
find함수는 find함수를 재귀적으로 돌리며 해당 트리 컴퍼넌트의 루트를 탐색해 반환한다.
재귀적으로 돌 때, 각 노드의 값을 루트 값으로 변형하며 컴퍼넌트의 노드가 해당 컴퍼넌트의 루트를 가리키도록 한다.
int find(int x) {
if (-1 == parent[x])
return x;
return parent[x] = find(parent[x]);
} merge함수는 인자로 들어온 두 노드가 같은 컴퍼넌트인지 판단하고,
다르다면 두 노드를 parent[a]=b 이런식으로 루트값을 넣어줌으로 이어준다.
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y)
parent[x] = y;
}다른 컴퍼넌트의 루트값을 인자로 넣어주면 두 컴퍼넌트가 합쳐진다.
따라서 크루스칼 알고리즘에서 간선을 비용에 대해 오름차순으로 정렬을 해주고,
앞에서부터 간선의 두 정점을 유니온파인드에 저장하고 두 정점이 어떤 컴퍼넌트에 있는지 판단한다.
두 정점이 다른 컴퍼넌트라면 merge함수를 통해 이어주고, answer에 비용값을 더한다.
두 정점이 같은 컴퍼넌트라면 패스한다.
다익스트라 알고리즘 변형 코드
#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include<algorithm>
using namespace std;
//시작섬, 도착섬 , 비용
vector<vector<pair<int,int>>> adj;
//비용, 섬
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
int shortest[101];
bool visited[101];
void dijkstra(int startNode){
pq.push({0,startNode});
shortest[startNode]=0;
pair<int,int> curNode;
while(!pq.empty()){
do
{
curNode=pq.top();
pq.pop();
} while(!pq.empty() && visited[curNode.second]);
//모든 큐 다 방문하고 마지막 curNode가 방문된거면 그냥 종료
if(visited[curNode.second]) return;
visited[curNode.second]=true;
for(auto elem : adj[curNode.second]){
if(visited[elem.first]) continue;
//각섬에 저장되어야하는 노드는 시작노드에서 시작해서 해당 노드로 갈때
//각섬에서 해당 섬으로 최소비용의 다리로만 갈수 있도록 해야함
//이렇게 하기위해서 모든 섬은 다리중에서 최소비용으로 짓고, 방문을 한 섬은 다시 방문x
if(shortest[elem.first] > elem.second)
{
shortest[elem.first]=elem.second;
pq.push({ elem.second,elem.first });
}
}
}
}
int solution(int n, vector<vector<int>> costs) {
int answer=2'100'000'000;
adj.resize(100);
for(auto elem : costs){
//양방향 그래프이다.
adj[elem[0]].push_back({elem[1],elem[2]});
adj[elem[1]].push_back({elem[0],elem[2]});
}
for(int i=0;i<n;i++){
int tmpAnswer=0;
fill(shortest,shortest+100,2'100'000'000);
fill(visited,visited+100,false);
dijkstra(i);
for(int j=0;j<n;j++){
if(!visited[i])continue;
tmpAnswer+=shortest[j];
}
answer=min(answer,tmpAnswer);
}
return answer;
}크루스칼 알고리즘
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// Union-Find 자료구조
class UnionFind {
public:
vector<int> parent;
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; ++i)
parent[i] = -1;
}
int find(int x) {
if (-1 == parent[x])
return x;
return parent[x] = find(parent[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y)
parent[x] = y;
}
};
int solution(int n, vector<vector<int>> costs) {
// 비용 순으로 정렬
sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b) {
return a[2] < b[2];
});
UnionFind uf(n);
int answer = 0;
for (const auto& cost : costs) {
int island1 = cost[0];
int island2 = cost[1];
int bridgeCost = cost[2];
if (uf.find(island1) != uf.find(island2)) {
uf.merge(island1, island2);
answer += bridgeCost;
}
}
return answer;
}
생각
크루스칼 알고리즘에 대해 배운 문제였고,
다익스트라를 각 노드에 한번만 방문하고, 최단거리만 저장하도록 변형하는 문제여서 많은 고민과
배움을 준 문제였다.
