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의 비용이 주어지지 않습니다.
- 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
- 연결할 수 없는 섬은 주어지지 않습니다.
입출력 예
입력 | n : 4, costs : [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]
출력 | 4
풀이
이 문제는 크루스칼 알고리즘을 활용해서 풀 수 있다.
크루스칼 알고리즘이란 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 알고리즘이다.
동작 순서는 다음과 같다.
1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트를 순서대로 확인하며 사이클을 형성하지 않는 간선을 찾는다.
3. 해당 간선을 집합에 추가한다.
섬 사이에 다리를 건설하는 비용이 주어졌으므로 가중치를 간선에 할당한 그래프가 될 수 있고, 최소의 비용으로 모든 섬을 연결해야하므로 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 크루스칼 알고리즘을 사용할 수 있는 것이다.
이 문제를 크루스칼 알고리즘의 동작 순서에 적용시켜 보면
1. 다리를 건설하는 비용에 따라서 costs 리스트를 오름차순으로 정렬한다.
2. 정렬된 costs 리스트의 첫번째 섬을 집합에 추가한다.
3. costs 리스트를 순서대로 확인하면서 사이클을 형성하지 않는 route, 즉 costs에 주어진 두 섬 중 하나만 집합에 포함되어 있는 route를 찾아서 해당 섬들을 집합에 추가하고 answer에 비용을 더한다. 그리고 더 이상 확인하지 못하게 임의의 리스트 [-1, -1, -1] 로 업데이트 해준다.
4. 이 작업을 routes에 모든 섬이 포함될 때까지 반복한다.
이렇게 코드를 짜면 되는데 바로 알고리즘이 생각나는 문제가 아니라 나중에 한 번 더 풀어봐야 할 것 같다😂
코드
def solution(n, costs):
answer = 0
# 비용을 기준으로 오름차순 정렬
costs.sort(key = lambda x:x[2])
routes = set([costs[0][0]])
# routes 집합에 모든 섬들이 포함될 때까지 반복
while len(routes) != n:
for i, cost in enumerate(costs):
# 두 섬 중 하나만 집합에 포함되어 있다면
if (cost[0] in routes and cost[1] not in routes) or (cost[1] in routes and cost[0] not in routes):
# 집합에 두 섬을 모두 추가, answer에 비용 더하기
routes.update([cost[0], cost[1]])
answer += cost[2]
costs[i] = [-1, -1, -1]
break
return answer