[1368] 물대기 - Java[자바]

 

 

| 문제 링크

 

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

1368번: 물대기

 

 

 

---

 

 

 

 

 

| 문제

 

 

1. 첫 줄의 논의 수 N이 주어집니다. N(1 ≤ N ≤ 300)
2. 두 번째 줄부터 N개의 줄에 N번 째 논에 우물을 파는 비용 Wi가 주어집니다. (1 ≤ Wi ≤ 100,000)
3. 다음 N개의 줄에 각 줄마다 N개의 수가 들어오는데 i번째 논과 j번째 논을 연결하는데 드는 비용이 주어닙니다.
   Pi,j(1 ≤ Pi,j ≤ 100,000, Pi,j = Pj,i, Pi,i = 0)
4. 우물을 파거나 논끼리 연결해 모든 논에 물을 공급하는 최소한의 비용을 출력하시오.

 

 

 

 

---

 

 

 

 

| 풀이

 

1. 모든 노드를 최소한의 비용으로 연결하는 최소 신장 트리 문제이며, 우물을 파거나 다른 논과 연결한다는 선택지가 두 개가 있다는 점을 고려해야합니다. 즉 한 개 이상의 논에서는 우물을 설치해야하며, 다른 논과 연결 하는 비용과 우물을 파는 비용을 비교해야합니다.
2. 크루스칼 방식으로 풀었으며, 0번째 부모 노드를 가상의 논으로 설정하여 한 개 이상의 우물을 설치하며, 우물을 판 논들도 연결될 수 있도록 해주었습니다.

 

 

 

자세한 내용은 아래 코드를 참고하시기 바랍니다.

 

 

 

 

---

 

 

 

 

 

| 코드

 

 

import java.io.*;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

class Node1368 implements Comparable<Node1368>{
	
	int from;
	int to;
	int w;
	
	public Node1368(int from, int to, int w) {
		this.from = from;
		this.to = to;
		this.w = w;
	}

	@Override
	public int compareTo(Node1368 o) {
		return w-o.w;
	}
	
}

public class Main {
	
	public static int n;
	public static int[] well;
	public static int[] parents;
	public static Queue<Node1368> pq = new PriorityQueue<>();

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		well = new int[n+1];	//i번째 논에 우물을 파는 비용
		parents = new int[n+1];	//논마다의 root
		
		for(int i = 1; i<=n; i++) {
			well[i] = Integer.parseInt(br.readLine());
			parents[i] = i;		//논마다 자기 자신을 default root로 가짐, 0번째 가상의 논은 default인 0 유지
		}
		
		for(int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 1; j <= n; j++) {
				int w = Integer.parseInt(st.nextToken());
				//중복되는 자료는 보지 않음
				if(i<j)
					continue;
				//자기 자신에게 우물을 파는 비용을 0번 인덱스를 활용해 가상의 논을 만들어줌
				else if(i==j)
					pq.add(new Node1368(0, i, well[i]));
				else
					pq.add(new Node1368(i, j, w));
			}
		}
		
		bw.write(String.valueOf(kruskal()));
		br.close();
		bw.close();
	}
	
	//root 찾기
	public static int find(int node) {
		if(parents[node] == node)
			return node;
		//root가 갱신되는 것을 계속해서 업데이트 해주기 위해 parents[node]의 값도 변경
		return parents[node] = find(parents[node]);
	}
	
	public static int kruskal() {
		int cost = 0;
		
		while(!pq.isEmpty()) {
			Node1368 now = pq.poll();
			int from = now.from;
			int to = now.to;
			
			if(find(from) != find(to)) {
				parents[find(from)] = find(to);
				cost+=now.w;
			}
		}
		
		return cost;
	}
	
}