문제:
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.
문제 풀이:
전형적인 Kruskal 알고리즘을 사용해서 푸는 문제이다. Kruskal 알고리즘이란, 탐욕적인 방법을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하는 방법이다. Kruskal 알고리즘을 사용하는 방법은 간단하다. 처음 시작하는 노드로 부터 하나의 간선을 선택해가면 된다.
이 문제의 예시로 설명을 들면 처음에 0에서 시작을 한다고 가정을 하자.
1. 0에 연결되어 있는 간선은 0-1(1), 0-2(2) 두 가지 간선이 있다. 최소 비용으로 연결하는 것이 목적이므로 0-1 간선을 선택하고 1의 노드를 연결된 노드 집합에 넣도록 한다.
2. 0과 1의 노드에 연결되어 있는 간선을 찾도록 하자. 그러면 0-2 (2), 1-2(5), 1-3(1) 세 가지 간선이 존재하게 되고, 역시 최소를 선택하므로 1-3을 선택하게 된다.
3. 위와 같은 방법으로 진행을 하면 0-2 간선을 선택하게 되어 모든 노드들이 연결되게 된다.
이제 이 방법들을 코드로 옮기면 다음과 같다. connect라는 연결된 노드 집합을 만들고 이 값이 n과 같게 되면 while이 끝나도록 한다. costs를 반복하여 connect에 있는 노드들의 간선을 찾도록 한다. (단 시점과 종점이 모두 connect에 있으면 안된다.) 이 간선들의 최소값을 찾아 answer에 더하고 connect 집합에 노드를 추가시키고 costs에서는 간선을 빼도록 한다. 이 작업을 모든 노드가 connect에 들어갈 때까지 반복한 answer를 반환하면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | def solution(n, costs): costs.sort() connect=[costs[0][0]] answer = 0 while len(connect)!=n: temp=1000000000000000 idx=0 for i in range(len(costs)): if costs[i][0] in connect or costs[i][1] in connect: if costs[i][0] in connect and costs[i][1] in connect: continue if temp > costs[i][2]: temp=costs[i][2] idx=i answer+=temp connect.append(costs[idx][0]) connect.append(costs[idx][1]) connect=list(set(connect)) costs.pop(idx) return answer | cs |
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1904. 01타일 (0) | 2019.07.10 |
|---|---|
| [Programmers]Lv 3. 기지국 설치 (0) | 2019.07.09 |
| [Programmers]Lv 3. 단속카메라 (2) | 2019.07.07 |
| [BOJ]2869. 달팽이는 올라가고 싶다. (0) | 2019.07.06 |
| [BOJ]1011. Fly me to the Alpha Centauri (0) | 2019.07.05 |