문제 설명
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를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.
내 풀이
def solution(n, costs): sorted_costs = sorted(costs, key = lambda x: x[2]) costs_sum = sorted_costs[0][2] path = set({sorted_costs[0][0], sorted_costs[0][1]}) sorted_costs.pop(0) while len(path) != n: for cost in sorted_costs: if cost[0] in path and cost[1] in path: continue elif cost[0] in path or cost[1] in path: path |= set({cost[0], cost[1]}) costs_sum += cost[2] sorted_costs.remove(cost) break return costs_sum
크루스칼 알고리즘을 썼다.
다만 간선들의 집합은 단 하나를 사용할 것이므로 이점을 고려해서 코드를 짰다.
우선 건설 비용에 따라 오름차순으로 정렬한 costs 리스트를 sorted_costs에 저장한다.
그리고 시작 경로를 path에 집합형태로 저장하고 건설 비용을 그 경로에 드는 비용으로 초기화한다.
경로로 확정된 요소는 리스트에서 제거할 것이다.
n이 커지면 pop 때문에 시간이 많이 소요 되겠지만 n은 100 이하이므로 그냥 pop 또는 remove를 썼다.
path의 크기는 n을 넘을 수 없다.
물론 넘을 수야 있지만 그러면 최소값이 되지 않는다.
정렬된 sorted_costs 리스트에서 하나씩 꺼내서 path에 이미 존재하는 경로인지를 확인한다.
이미 path에 존재하는 경로에 대해서는 작업을 하지 않고 cost의 시작과 끝 점, cost[0]과 cost[1] 중에 하나라도 path에 없는 것이 있다면 path 집합을 신장할 것이다.
costs_sum에 cost[2]를 더해주고 경로가 확정됐으므로 remove해준다.
cost[0]와 cost[1] 둘 다 path에 없는 경우에도 기본적인 크루스칼 알고리즘에 의하면 추가를 해주는 것이 맞는데, 그렇게 되면 앞서 말했듯이 path 집합을 여러개 써야 하므로 코드가 복잡해진다.
시간복잡도가 그렇게 크지 않으므로 효율성보다 구현의 간편함을 택했다.
