[백준] 10423. 전기가 부족해 (Java)

 

문제

10423번: 전기가 부족해

 

알고리즘

그래프 이론, 최소 스패닝 트리, 크루스칼 알고리즘

 

풀이

모든 도시에 전기를 공급하기 위한 케이블 연결의 최소 비용을 구하는,

즉 모든 정점을 잇는 간선의 최소 비용을 구하는 최소 스패닝 트리 문제로 크루스칼 알고리즘을 사용하여 해결하였다.

 

이미 발전소가 지어져있고, 한 도시는 하나의 발전소에서만 전기를 공급 받아야하므로

두 도시를 연결할 때, 두 도시의 루트 노드가 발전소라면 두 발전소에서 전기를 공급받게 되므로 연결하면 안된다.

 

이를 위해서 발전소가 지어진 정점의 parent 값을 i가 아닌 -1로 동일하게 초기화하여 각 발전소를 이미 연결한 것처럼 만든다.

또 발전소와 연결된 도시와 그렇지 않은 도시를 연결할 때 -1 을 루트로 하도록 union 하여 구조를 유지한다.

 

따라서 두 정점이 모두 발전소와 연결되어있다면 find 값이 둘 다 -1이 되어, 특별한 구현 없이 진행하지 않고 넘어갈 수 있다.

 

정점을 연결한 후 모든 노드의 루트가 -1 이라면 모든 도시가 전기를 공급받는 것이므로 더 이상 진행하지 않고, 누적된 값을 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int[] parent;
	static PriorityQueue<Edge> pq;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		parent = new int[N + 1];
		for (int i = 1; i <= N; i++)
			parent[i] = i;

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < K; i++)
			parent[Integer.parseInt(st.nextToken())] = -1;

		pq = new PriorityQueue<>();
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			pq.add(new Edge(u, v, w));
		}

		System.out.println(kruskal());
	}

	static int kruskal() {
		int sum = 0;

		while (!pq.isEmpty()) {
			Edge edge = pq.poll();

			if (find(edge.from) != find(edge.to)) {
				sum += edge.weight;
				union(edge.from, edge.to);
				
				if(connect()) break;
			}
		}

		return sum;
	}

	static boolean connect() {
		for(int i=1; i<parent.length; i++) {
			if(parent[i] != -1)
				return false;
		}
		
		return true;
	}

	static void union(int a, int b) {
		a = find(a);
		b = find(b);

		if (a == -1)
			parent[b] = -1;
		else if (b == -1)
			parent[a] = -1;
		else
			parent[a] = b;
	}

	static int find(int a) {
		if (parent[a] == -1)
			return -1;

		if (a == parent[a])
			return a;

		return parent[a] = find(parent[a]);
	}

	static class Edge implements Comparable<Edge> {
		int from, to, weight;

		public Edge(int from, int to, int weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return weight - o.weight;
		}
	}
}