240206 섬 연결하기

public int solution(int n, int[][] costs) {
	Map<Integer, List<int[]>> graph = new HashMap<>();
	for (int[] cost : costs) {
		graph.computeIfAbsent(cost[0], k -> new ArrayList<>()).add(new int[] { cost[1], cost[2] });
		graph.computeIfAbsent(cost[1], k -> new ArrayList<>()).add(new int[] { cost[0], cost[2] });
	}

	PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(arr -> arr[1]));
	Set<Integer> visited = new HashSet<>();
	int totalCost = 0;

	pq.addAll(graph.get(0));
	visited.add(0);

	while (!pq.isEmpty()) {
		int[] edge = pq.poll();
		int vertex = edge[0];
		int cost = edge[1];

		if (visited.contains(vertex)) {
			continue;
		}

		visited.add(vertex);
		totalCost += cost;

		if (graph.containsKey(vertex)) {
			for (int[] neighbor : graph.get(vertex)) {
				if (!visited.contains(neighbor[0])) {
					pq.offer(neighbor);
				}
			}
		}
	}

	return totalCost;
}

출처:https://school.programmers.co.kr/learn/courses/30/lessons/42861