백준 | 3803번. Networking - 최소 스패닝 트리 문풀

⬛ 백준 3803번. Networking - 최소 스패닝 트리 문풀

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

3803번: Networking

문제

당신은 넓은 지역의 특정 지점 사이의 네트워크 연결을 설계하는 임무를 맡았습니다. 해당 영역에 일련의 점과 점 쌍을 연결할 수 있는 케이블에 대한 가능한 경로 세트가 제공됩니다. 두 지점 사이의 가능한 각 경로에 대해 해당 경로의 지점을 연결하는 데 필요한 케이블 길이가 제공됩니다. 주어진 두 지점 사이에는 가능한 경로가 많이 있을 수 있습니다. 주어진 가능한 경로는 해당 지역의 각 두 지점을 (직접 또는 간접적으로) 연결한다고 가정합니다. 귀하의 임무는 모든 두 지점 사이에 연결(직접 또는 간접)이 있도록 해당 영역에 대한 네트워크를 설계하는 것입니다(즉, 모든 지점은 상호 연결되지만 반드시 직접 케이블을 사용할 필요는 없음). 사용되는 케이블은 최소화됩니다.

입력

입력 파일은 여러 데이터 세트로 구성됩니다. 각 데이터 세트는 하나의 필수 네트워크를 정의합니다. 세트의 첫 번째 줄에는 두 개의 정수가 포함되어 있습니다. 첫 번째 줄은 주어진 지점의 수 P를 정의하고 두 번째 줄은 지점 사이의 주어진 경로 수 R을 정의합니다. 다음 R 선은 지점 사이의 주어진 경로를 정의하며 각각 3개의 정수 번호를 제공합니다. 처음 두 숫자는 지점을 식별하고 세 번째 숫자는 경로의 길이를 제공합니다. 숫자는 공백으로 구분됩니다. 하나의 숫자 P=0만 제공하는 데이터 세트는 입력의 끝을 나타냅니다. 데이터 세트는 빈 줄로 구분됩니다.

최대 지점 수는 50개입니다. 주어진 경로의 최대 길이는 100개입니다. 가능한 경로 수는 무제한입니다. 노드는 1과 P(포함) 사이의 정수로 식별됩니다. 두 지점 i와 j 사이의 경로는 ij 또는 j i로 주어질 수 있습니다.

출력

각 데이터 세트에 대해 전체 설계된 네트워크에 사용되는 케이블의 총 길이를 나타내는 하나의 숫자를 별도의 줄에 인쇄하십시오.

---

💚나의 풀이

이 문제는 주어진 케이스별로 최소 스패닝 트리를 이용하여 ‘최소 비용’을 출력하는 문제였다.

1) P와 R을 입력받는다.

• P가 0일 때 입력 끝을 의미한다.
• P = 노드 개수, R = 간선 개수이다.

2) 최소 비용 신장트리 문제는 노드개수-1개의 간선을 사용하여 최소비용을 구성해야 한다는 점을 유의하자.

3) PriorityQueue는 자동으로 노드의 가중치 작은 값을 기준으로 정렬해주기 때문에 여기에 R개의 간선 정보를 입력해두고, while문을 돌면서 사이클을 형성 하지 않는 N-1개 간선만 추가한 뒤 그 최소비용 값을 출력하면 된다.

package to_1101_2;

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

/**
 * 3803번. Networking - 최소비용 신장트리 문풀 
 * @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 this.val - o.val;
	}
}
public class Main {
	static int P, R;
	static int[] parent;
	static PriorityQueue<Edge> pQ;
	
	//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;
		}
	}
	
	//mst
	static int MST(PriorityQueue<Edge> pQ) {
	
		int useEdge = 0;
		int useCost = 0;
		while(useEdge<P-1) {
			Edge cur = pQ.poll();
			
			if(find(cur.s) != find(cur.e)) {
				union(cur.s, cur.e);
				useCost += cur.val;
				useEdge ++;
			}
		}
		return useCost;
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		
		while(true) {
			P = kb.nextInt();
			if(P == 0) break;
			R = kb.nextInt();
			
			parent = new int[P+1];
			for(int i=1; i<=P; i++) parent[i] =i;
			
			pQ = new PriorityQueue<>();
				
			for(int i=0; i<R; i++) {
				int a = kb.nextInt();
				int b = kb.nextInt();
				int c = kb.nextInt();
				pQ.offer(new Edge(a, b, c));
			}
			
			System.out.println(MST(pQ));
		}
	}
}