Programmers 42861: 섬 연결하기

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);
	}
}