백준 | 1368번. 물대기 - 최소 비용 신장 트리 (크루스칼) 문풀

⬛ 백준 1368번. 물대기 - 최소 비용 신장 트리 (크루스칼) 문풀

https://www.acmicpc.net/problem/1368

1368번: 물대기

문제

선주는 자신이 운영하는 N개의 논에 물을 대려고 한다. 물을 대는 방법은 두 가지가 있는데 하나는 직접 논에 우물을 파는 것이고 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다.

각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때 최소의 비용으로 모든 논에 물을 대는 것이 문제이다.

입력

첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어오는데 이는 i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j(1 ≤ Pi,j ≤ 100,000, Pi,j = Pj,i, Pi,i = 0)를 의미한다.

출력

첫 줄에 모든 논에 물을 대는데 필요한 최소비용을 출력한다.

---

💚 문제 접근 방식

• 물을 대는 방법은 2가지이다. 1) 직접 파기 2) 간접 끌어오기
• 이 문제에서 주의할 점은 직접 우물 파는 경우에 대한 간선 Edge 를 담기 위해 0번을 가상 정점으로 추가했다는 점이다. 무지성으로 N개 정점에 대한 간선 N-1개 연결하려고 하면 직접 파는 경우를 제외하게 된다.
• (결과적으로 0번 포함한 N+1 개의 정점을 사용한 것이니, 최소비용을 연결할 간선은 N개 필요하다.)
• 가상 정점 0번에 대해서는 (자기 자신에 대한 우물을 직접 파는 비용)으로 연결하고, 나머지는 연결 비용 값은 들어온 2차원 배열 상의 값으로 간선 Edge 를 세팅해서 pQ에 담는다.
• 그리고 가중치 작은 값을 우선으로 정렬 되기 에 pQ에 뽑아서 차례대로 정점을 연결(union)하다 보면 결과적으로 모든 정점이 최소 비용으로 연결되어 있을 것이다.

풀이 설명 그림

💡 N-1개의 간선으로 먼저 연결하고 가장 작은 비용으로 직접 우물 파는 정점의 비용을 더하면 안되냐 ?
 - 안 된다. 직접 우물파는 비용이 최솟값을 가져도 해당 정점과 연결하는 비용이 되려 더 커질 경우, 결과적으로 모든 정점을 최소 비용으로 잇지 못하는 불상사가 생긴다.

💚 제출 코드

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * 1368번. 물대기 - MST
 * @author MYLG
 *
 */
class Edge implements Comparable<Edge>{
	int st, ed, val;
	
	Edge(int st, int ed, int val){
		this.st = st;
		this.ed =ed;
		this.val=val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;//가중치 오름차순 정렬
	}
}
public class Main {
	static int N;
	static int[] w;
	static int[] parent;
	
	//find
	static int find(int a) {
		if(a == parent[a]) return a;
		else return parent[a] = find(parent[a]);
	}
	
	//union
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		
		if(a != b) {
			parent[b]= a;
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N= kb.nextInt();
		w = new int[N+1];
		
		//자기 자신으로 초기화 
		parent = new int[N+1];
		for(int i=1; i<=N; i++) parent[i] = i;
		
		for(int i=1; i<=N; i++) w[i] = kb.nextInt();
		
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		
		//간선 채우기 
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				int p = kb.nextInt();//연결 비용 
				if(i == j) {
					//자기 자신에 대해서는 직접 우물 파는 비용 담기 - 가상 노드 0에 잇기
					pQ.offer(new Edge(i, 0, w[i]));
				}else {
					pQ.offer(new Edge(i, j, p));
				}
			}
		}
		
		//크루스칼
		int useCost = 0;
		
		while(!pQ.isEmpty()) {
			Edge cur = pQ.poll();
			if(find(cur.st) == find(cur.ed)) continue;
			
			union(cur.st, cur.ed);
			useCost+=cur.val;
		}
		
		System.out.println(useCost);
	}
}