[백준] 1368. 물대기 (Java)

 

문제

1368번: 물대기

 

알고리즘

그래프, 최소 스패닝 트리

 

풀이

최소 하나의 논, 혹은 여러 논에 우물을 파고,

이를 이용해서 모든 논을 이어야하는 최소 스패닝 트리 문제이다.

 

따라서 우물을 파는 것을 다른 하나의 논(0번 논)에서 물을 끌어오는 것으로 생각하면 단순한 최소 스패닝 트리 문제가 된다.

다음은 예제 입력 1 그래프와 0번 논을 추가한 그래프이다.

예제 입력1 그래프와 0번 노드를 추가한 그래프

 

따라서 우물을 파는 비용을 0번 노드와 i번 노드의 가중치로 만들고, 크루스칼 알고리즘을 이용해 모든 정점을 잇는 최소 비용을 구해 출력한다.

 

 

코드

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

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

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

		int N = Integer.parseInt(br.readLine());
		pq = new PriorityQueue<>();
		parent = new int[N + 1];
		
		for (int i = 1; i <= N; i++) {
			parent[i] = i;
			
			int weight = Integer.parseInt(br.readLine());
			pq.add(new Edge(0, i, weight));
		}

		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 1; j <= N; j++) {
				int weight = Integer.parseInt(st.nextToken());
				if (i == j)
					continue;
				pq.add(new Edge(i, j, weight));
			}
		}

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

	static int kruskal() {
		int sum = 0;

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

			if (union(edge.from, edge.to))
				sum += edge.weight;
		}

		return sum;
	}

	static boolean union(int from, int to) {
		int a = find(from);
		int b = find(to);

		if (a == b)
			return false;

		parent[a] = b;
		return true;
	}

	static int find(int a) {
		if (parent[a] == 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;
		}
	}
}