n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하는 문제이다.
=> 최소비용신장트리 중 Prim 알고리즘 사용
최소비용신장트리:
2020/07/19 - [알고리즘 공부/boj] - boj 1197: 최소 스패닝 트리
import java.util.*;
class Solution {
public int solution(int v, int[][] costs) {
LinkedList<Edge>[] pair = new LinkedList[v + 1];
HashSet<Integer> vSet = new HashSet<Integer>();
for (int i = 0; i < v; i++) {
pair[i] = new LinkedList<Edge>();
vSet.add(i);
}
for (int i = 0; i < costs.length; i++) {
int start = costs[i][0];
int end = costs[i][1];
long cost = costs[i][2];
pair[start].add(new Edge(end, cost));
pair[end].add(new Edge(start, cost));
}
int currentNode = 1;
int answer = 0;
vSet.remove(1);
PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
pq.addAll(pair[currentNode]);
while (!vSet.isEmpty()) {
Edge minEdge = pq.poll();
if (vSet.contains(minEdge.v)) {
answer += minEdge.cost;
currentNode = minEdge.v;
vSet.remove(currentNode);
pq.addAll(pair[currentNode]);
}
}
return answer;
}
}
class Edge implements Comparable<Edge> {
int v;
long cost;
public Edge(int v, long cost) {
this.v = v;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return Long.compare(this.cost, o.cost);
}
}
'알고리즘 공부 > programmers' 카테고리의 다른 글
Programmers 42891: 무지의 먹방 라이브 (0) | 2021.01.24 |
---|---|
Programmers 67258: 보석 쇼핑 (0) | 2021.01.22 |
Programmers 67260: 동굴 탐험 (0) | 2021.01.17 |
Programmers 62050: 지형 이동 (0) | 2021.01.17 |
Programmers 64062: 징검다리 건너기 (0) | 2021.01.17 |