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

섬 연결하기

문제 링크

섬 연결하기

분석

최소 비용으로 모든 섬을 연결해주어야 합니다.
이 경우 최소 신장 트리를 사용해볼 수 있습니다.
최소 신장 트리는 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프입니다.

알고리즘은 크루스칼 알고리즘 혹은 프림 알고리즘을 이용할 수 있습니다.

DFS, BFS 알고리즘은 모든 정점을 방문 할 수 있지만, 최소 비용으로 정점을 이을 수는 없습니다.
다익스트라는 모든 정점을 방문하지만, 경로의 비용 최소화이지, 전체 그래프를 최소 비용으로 연결하지 않습니다.

임의의 i에 대해 costs[i][0]와 costs[i][1]에는 다리가 연결되는 두 섬의 번호가 들어있습니다.
costs[i][2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.

같은 연결은 두 번 주어지지 않으며, 순서가 바뀌더라도 같은 연결로 봅니다.
즉, 무방향 간선이며, 중복 간선은 존재하지 않습니다.

연결할 수 없는 섬은 주어지지 않습니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

// 유니온 파인드 알고리즘의 find 연산
// 특정 노드 x의 루트 부모를 찾는다.
int findParent(vector<int>& parent, int x)
{
    if (parent[x] == x)
    {
        return x;
    }
    
    // 재귀적으로 부모를 찾아가며, 부모 노드를 바로 루트로 연결한다.
    return parent[x] = findParent(parent, parent[x]);
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    // 각 섬의 부모를 저장하는 벡터
    vector<int> parent(n);
    
    // 초기값으로 자기 자신을 부모로 설정한다.
    for (int i = 0; i < n; ++i)
    {
        parent[i] = i;
    }
    
    // 간선을 비용 기준으로 오름차순 정렬한다.
    // 가장 적은 비용의 다리부터 연결을 시도한다.
    sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b)
         {
             return a[2] < b[2];
         });
    
    // 정렬된 간선을 순회한다.
    for (const auto& edge : costs)
    {
        // 순서대로 첫 번째 섬, 두 번째 섬, 다리 건설 비용
        int a = edge[0];
        int b = edge[1];
        int cost = edge[2];
        
        // 각 섬의 루트 부모를 찾는다.
        int aParent = findParent(parent, a);
        int bParent = findParent(parent, b);
        
        // 사이클이 발생하지 않는 경우 두 집합을 합친다.
        if (aParent != bParent)
        {
            // 더 작은 번호를 부모로 설정한다.
            if (aParent < bParent)
            {
                parent[bParent] = aParent;
            }
            else
            {
                parent[aParent] = bParent;
            }
            
            // 간선을 MST에 추가하므로, 비용 추가
            answer += cost;
        }
    }
    
    return answer;
}

유니온 파인드 알고리즘으로 find 연산을 수행하는 경우, 경로 압축을 통해 시간 복잡도를 최적화 합니다.

성능 요약

시간 복잡도는 $O(e \ log \ e)$입니다.

• 각 섬의 부모를 저장하는 벡터 초기화 반복문 $O(n)$
  • n은 섬 개수
• 정렬 $O(e \ log \ e)$
  • e는 간선의 개수
• 유니온 파인드 연산 $O(e \times \alpha(n))$
  • $\alpha(n)$는 아커만 역함수로, 매우 느리게 증가하므로 실질적으로 $O(1)$입니다.
• $O(n) + O(e \ log \ e) + O(e \times \alpha(n))$

공간 복잡도는 $O(n)$입니다.

• 각 섬의 부모를 저장하는 벡터 vector<int> parent $O(n)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 3.69MB)
테스트 3 〉 통과 (0.01ms, 4.15MB)
테스트 4 〉 통과 (0.01ms, 4.15MB)
테스트 5 〉 통과 (0.01ms, 4.22MB)
테스트 6 〉 통과 (0.02ms, 3.68MB)
테스트 7 〉 통과 (0.01ms, 4.21MB)
테스트 8 〉 통과 (0.01ms, 3.69MB)