백준 | 7044번. Bad Cowtractors - 최소 비용 신장 트리 문풀

⬛ 백준 7044번. Bad Cowtractors - 최소 비용 신장 트리 문풀

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

7044번: Bad Cowtractors

문제

Bessie는 편리한 번호 1..N인 Farmer John의 N(2 <= N <= 1,000) 헛간 사이에 저렴한 인터넷 네트워크를 구축하기 위해 고용되었습니다. FJ는 이미 몇 가지 조사를 수행하여 헛간 쌍 사이에 M(1 <= M <= 20,000)개의 가능한 연결 경로를 찾았습니다. 가능한 각 연결 경로에는 관련 비용 C(1 <= C <= 100,000)가 있습니다. 농부 John은 네트워크 연결에 최소한의 비용을 지출하기를 원합니다. 그는 Bessie에게 돈을 지불하고 싶지도 않습니다.

농부 John이 그녀에게 돈을 지불하지 않을 것이라는 사실을 깨달은 Bessie는 가능한 최악의 일을 하기로 결정합니다. 그녀는 (i) 이러한 연결의 총 비용이 가능한 한 크고, (ii) 모든 헛간이 함께 연결되도록(다른 헛간에서 헛간에 도달할 수 있도록) 설치할 연결 세트를 결정해야 합니다. 설치된 연결 경로를 통해) (iii) 연결 사이에 순환이 없도록 해야 합니다(Farmer John이 쉽게 감지할 수 있음). 조건 (ii)와 (iii)은 최종 연결 세트가 "트리"처럼 보이도록 보장합니다.

입력

• 1행: 공백으로 구분된 두 정수: N 및 M
• 2..M+1행: 각 행에는 비용이 C인 헛간 A와 B 사이의 연결 경로를 설명하는 공백으로 구분된 3개의 정수 A, B, C가 포함되어 있습니다.

출력

• 1행: 모든 헛간을 연결하는 가장 비싼 나무의 가격을 포함하는 단일 정수입니다. 모든 헛간을 연결할 수 없으면 -1을 출력합니다.

---

💚나의 풀이

• 문제의 기본 기조는 ‘최소 비용 신장 트리’를 따른다.
• 다만, 문제에 나와있듯이, Bassie는 가능한 최악의 일을 하기로 결정한 상태이다.
• 따라서 최소 비용 신장 트리의 풀이에서, 모든 가중치 합이 ‘최대’가 되도록 바꿔서 풀면 해결되는 문제였다.
• 또한, 모든 헛간을 연결할 수 없다면 -1을 출력하는 부분은 while() 문으로 사용한 간선을 N-1이 될 때까지 반복할 때, 아직 N-1개의 간선도 사용하지 않았는데 pQ에서 뽑은 Edge 가 null인 경우에 해당한다.
• 즉, 아직 연결이 미완성 상태인데 다음 사용할 엣지가 pQ에 존재하지 않는 것이므로, 모든 헛간을 연결할 수 없다는 말이다.

---

🟦 풀이 순서

1. PriorityQueue<edge> pQ 에 차례대로 간선의 정보를 ‘가중치 내림차순’으로 담는다.

2. while(useEdge ≠ N-1) 인 동안 반복한다.

• 정점은 N개 이므로, 간선은 N-1개가 되어야 한다.
• 사이클을 형성하지 않는 한도 내에서 최대 가중치 갖는 간선을 차례대로 N-1개 사용하며 연결시키면 된다.

3. 만약 while()문 안에서 간선 n-1개 사용 전, pQ상에 Edge가 null 상태가 된다면 모든 헛간 연결 불가능한 상태이므로 -1을 출력한다.

4. 그게 아니라면 사이클 형성하지 않도록 연결하며 누적한 useCost 비용을 그대로 출력한다.

---

🟦 코드

package to_1122_7;

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

/**
 * 7044번. 나쁜 소트랙터들 = 최소 스패닝 트리 문풀 
 * @author MYLG
 *
 */
class Edge implements Comparable<Edge>{
	int s, e, val;
	Edge(int s, int e, int val){
		this.s = s;
		this.e = e;
		this.val = val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return o.val - this.val;//내림차순 정렬 되도록 
	}
}
public class Main {
	static int N, M;
	static int[] parent;
	static PriorityQueue<Edge> pQ;
	
	//find
	static int find(int a) {
		if(a == parent[a]) return a;
		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();
		M = kb.nextInt();
		
		parent = new int[N+1];
		for(int i=1; i<=N; i++) parent[i] = i;//자기 자신으로 초기화
		
		pQ = new PriorityQueue<>();
		
		for(int i =0; i<M; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int val = kb.nextInt();
			pQ.offer(new Edge(a, b, val));
		}
		
		int useEdge = 0;
		int useCost = 0;
		
		boolean flag = false;
		while(useEdge != N-1) {
			Edge cur = pQ.poll();
			if(cur == null) {
				flag = true;
				break;
			}
			
			if(find(cur.s) != find(cur.e)) {
				union(cur.s, cur.e);
				useCost += cur.val;
				useEdge++;
			}
		}
		
		if(flag == true) {
			System.out.println(-1);
		}else {
			System.out.println(useCost);
		}	
	}
}