[프로그래머스/C++] 섬 연결하기 (MST 알고리즘)

섬 연결하기

문제 설명

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

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

---

해당 문제는 최소 신장 트리(스패닝 트리)를 만드는 문제이다.

 

📌 최소 신장 트리에 대한 설명은 게시글에 따로 정리해두었다.

2023.09.21 - [💻코딩테스트/알고리즘, 자료구조] - [자료구조] 최소 신장 트리 - 크루스칼/프림 알고리즘

[자료구조] 최소 신장 트리 - 크루스칼/프림 알고리즘

 

나는, 최소 신장 트리 알고리즘인 크루스칼과 프림 중, 크루스칼 알고리즘을 이용해 문제를 풀이했다.

 

위 게시글에도 나와있지만 간단히 설명하자면, 크루스칼 알고리즘은 모든 정점을 가장 적은 비용으로 연결하는 알고리즘으로, 가중치가 가장 낮은 간선을 선택하되, 사이클의 형성 여부를 판별하며 MST 집합에 간선을 포함하는 단계로 이루어진다.

 

말로하니까 굉장히 복잡하게 느껴지는데 사실, Union-Find 알고리즘만 이해하면 그렇게 어렵지 않다.

(예전에 백준에서 최소 신장 트리 문제를 풀어봤기 때문에 해당 문제도 많이 헤매이지 않았다)

 

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

using namespace std;

vector<int> parent(101);

int Find(int x)
{
	if (x == parent[x])
		return x;

	return parent[x] = Find(parent[x]);
}

bool Union(int a, int b)
{
	a = Find(a);
	b = Find(b);

	if (a == b)
		return false;

	if (a > b)
		parent[a] = b;
	else
		parent[b] = a;

	return true;
}

// [0]-[1]: 연결된 노드, [2]:비용
int solution(int n, vector<vector<int>> costs) {
	int answer = 0;
	
	sort(costs.begin(), costs.end(), [](const vector<int>& cost1, const vector<int>& cost2){
		return cost1[2] < cost2[2];
	});

    for (int i = 1; i <= n; i++)
		parent[i] = i;
    
	for(int i = 0; i < costs.size(); i++)
	{
		if (Union(costs[i][0], costs[i][1]))
			answer += costs[i][2];
;	}

	return answer;
}

 

풀이 과정은 아래와 같다.

 

1. 그래프 vector를 간선의 가중치가 작은 순서대로, 오름차순 정렬한다.

2. 사이클을 판별하기 위한 부모 노드 vector인 parent를 초기화한다.
   초기화 단계에선 1번 노드부터 n번 노드까지 각각은 자신이 부모노드인걸로 초기화된다.

3. 가중치가 작은 0번째 인덱스 간선부터 끝까지 for문을 돌며, 사이클이 형성되는지 검사하고, MST 집합에 포함하며 부모 노드 정보를 갱신한다.

4. 사이클이 형성되지 않는다면 비용을 담는 변수 answer에 가중치를 더한다.

 

여기서, 사이클을 판단하는 Union - Find 알고리즘은 서로소 집합 Disjoint Set 자료구조를 통해 구현할 수 있다.

서로 다른 두 집합을 병합하는 Union 연산과, 집합 원소가 어떤 집합에 속해있는지 찾는 Find 연산을 각각 구현하면 된다. (Union이 합집합을 의미한다)

 

Find 함수는 부모 노드를 저장했던 parent 배열을 참고하여, 재귀함수를 통해 현재 노드 x에서 x의 부모, x의 부모의 부모, ... 처럼 최종 부모 노드를 찾아 반환하는 함수이다.

 

Union 함수에서 두 집합을 병합할 때, 부모노드가 같다면 두 수가 동일한 집합군에 속해있기 때문에 Union의 실행 결과를 false로 반환한다.

부모노드가 같지 않다면, 더 큰 정수의 부모노드에 작은 정수를 자식으로 포함하여 집합을 병합한다.

 

이러한 원리만 이해한다면 사실 최소 비용 신장 트리는 그렇게 어려운 문제가 아니다.

알고리즘과 자료구조는 늘 모르고 있을 때가 가장 어렵지 이해하고 있다면 구현 문제보다 약간은 쉽게 풀리는 것 같다...! (근데 가끔 구현보다 안풀릴때도 있긴 해서 자만하면 안된다.)

---

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스