개요

링크텍스트

• 문제 설명
  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의 비용이 주어지지 않습니다.
  모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
  연결할 수 없는 섬은 주어지지 않습니다.

접근 방식

다익스트라 알고리즘 변형

1. 우선 처음 봤을 때 최소의 비용으로 모든 섬을 통행가능하다고 한걸 보자마자 다익스트라 알고리즘이 떠올랐다.
   다익스트라 알고리즘으로 코드를 짜고 각 노드의 최단 경로 비용이 갱신이 될 때 map을 이용해 연결된 섬들을 다 저장했다.
   마지막에 map을 순회하며 비용들을 계산하는 식으로 풀었으나 틀렸다.

2. 그래서 아! 다른 노드에서 시작을 한다면 값이 다르겠구나라는 생각을 떠올리고,
   n도 최대값이 100으로 적은 숫자라 모든 노드에서 위 방식대로 다익스트라를 한번씩 돌리고 map을 순회하며 계산한 비용 중에 최소값을 구했지만 틀렸다.

3. 이거저거 찾아보고 고민한 결과 이유는 다익스트라 알고리즘은 한 섬에서 출발해
   다른 섬으로 가는 최단경로를 구하는 방식으로, 이 문제와는 안 맞다.

   이 문제에서 요구하는 부분은 각 섬에서 인근 섬까지의 최저 간선 비용만을 구해 합산하는 것으로,
   각 섬에서 다른 모든 섬으로 최단경로를 구해 간선 비용을 구하는게 아니다.
   

4. 따라서 섬에서 다른 섬으로 이동할 때, 모든 경로중 최단 경로를 구하는게 아니라
   그리디 알고리즘 방식으로 각 섬에서 바로 옆섬으로 이동할 때의 최소비용의 간선만 고른 후,
   이동한 섬은 다시 안 보는 식으로 구현하면 된다.

5. 이를 위해선 다익스트라알고리즘을 변형을 좀 해야한다.

   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가 더 줄어들 수 있다면 갱신을 해줬는 데,
   이제는 각 섬에서 다른 섬으로 최소비용의 간선만 택하고 이미 방문한 섬은 쳐다보지도 않는다.

6. 이렇게 실행하면 shortest배열의 각 index에 저장된 값은
   이전 index 섬에서 해당 index의 섬으로 연결된 간선의 최소비용이다.
   모든 노드에서 visited배열에 true체크되어있는 노드를 체크한다.
   shortest배열의 인덱스가 해당 노드인 값을 조사해 최저 간선비용들을 구하면 된다.
   하지만, 이 방식도 결국 시작노드를 어디서부터 하냐에 따라 차이가 나게 되므로
   시작노드에 반복문을 통해 모든 노드를 넣고 실행한 후 최소값을 추출해야한다.

크루스칼 알고리즘

크루스칼 알고리즘은 최소 스패닝 트리를 만드는 알고리즘이다.
간선을 정렬 후 최소값의 간선부터 컴퍼넌트로 연결한다는 점에서 그리디 알고리즘을 따른다.
최소 스패닝 트리는 간선마다 가중치가 있는 트리에서, 가중치의 합이 최소가 되는 트리이다.
크루스칼 알고리즘의 방식은

1. 간선을 오름차순으로 우선 정렬한다.

2. 해당 간선의 두 정점이 이미 연결된 컴퍼넌트 내부에 있다면 패스하고,
   두 정점이 연결이 안 되어 있다면 연결해준다.

3. 간선을 정점-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;
}

생각

크루스칼 알고리즘에 대해 배운 문제였고,
다익스트라를 각 노드에 한번만 방문하고, 최단거리만 저장하도록 변형하는 문제여서 많은 고민과
배움을 준 문제였다.