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

문제 설명

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

 

 

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> parent;

int cmp(vector<int> a, vector<int> b)
{
    return a[2] < b[2];
}

int getParent(int a)
{
    if (parent[a] == a)
        return a;
    return getParent(parent[a]);
}

int isCycle(int a, int b)
{
    a = getParent(a);
    b = getParent(b);
    if (a == b)
        return true;
    return false;
}

void unionParent(int a, int b)
{
    a = getParent(a);
    b = getParent(b);
    if (a < b)
        parent[b] = a;
    else
        parent[a] = b;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    int i;
    int a, b;
    
    sort(costs.begin(), costs.end(), cmp);
    for (i = 0; i < n; i++)
    {
        parent.push_back(i);
    }
    for (i = 0; i < costs.size(); i++)
    {
        a = costs[i][0];
        b = costs[i][1];
        if (isCycle(a, b))
            continue;
        answer += costs[i][2];
        unionParent(a, b);
    }
    return answer;
}

 

크루스칼 알고리즘을 사용하여 풀었다.

1. 간선을 비용에 대한 오름차순으로 정렬한다.
2. 모든 노드의 부모를 자기 자신으로 초기화한다.
3. 비용이 작은 간선부터 사용해 두 개의 노드를 연결한다. 이때, 사이클이 만들어지면 연결하지 않는다. 연결된 두 노드의 부모는 둘 중 더 작은 값으로 바꿔준다.

 

링크

programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

github.com/inbdni/Programmers/blob/master/level03/%EC%84%AC%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0.cpp

inbdni/Programmers