[스위프트 알고리즘] 프로그래머스: 섬 연결하기

문제

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

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

문제 설명

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. 간선들을 간선 가중치 오름차순으로 정렬한다. 
2. 가장 비용이 적은 간선부터 꺼내서 최소신장트리에 추가한다. 
3. 최소신장트리에 추가했을 때 사이클이 발생하는 간선이라면 트리에서 제외한다. 
4. 모든 간선들을 다 확인할 때까지 2, 3번 과정을 반복한다.

여기서 가장 관건이 되는 포인트는 사이클 발생을 체크하는건데요, 유니온 파인드를 통해 사이클 확인도 쉽게할 수 있습니다. 저는 유니온 파인드의 합집합 연산인 Union 연산의 반환 값을 Bool 값으로 설정해서 만약 이미 같은 조상 노드를 가진, 같은 집합에 포함된 정점들이라면 false를, 그렇지 않다면 합집합 연산을 수행하고 true를 반환하도록 했습니다. 

 

쉽게말하면, 같은 조상노드 A를 가지고 있는 집합의 원소인 B 와 C를 서로 연결하게되면 A->B->C->A 의 사이클이 발생하기 때문에 연산을 수행하지 않고 곧바로 false를 반환하는 것입니다! 

 

이 문제에서는 직접적으로 트리를 만들 필요없이 간선 가중치의 합만 구하면 되기 때문에, Union 연산에서 true가 반환된 정점 사이에 간선 가중치들의 합을 구해 정답으로 반환했습니다.

 

코드