백준 16398번. 행성 연결 - 최소비용 신장 트리

⬛ 백준 16398번. 행성 연결 - 최소비용 신장 트리

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

16398번: 행성 연결

문제

홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다.

두 행성 간에 플로우를 설치하면 제국의 함선과 무역선들은 한 행성에서 다른 행성으로 무시할 수 있을 만큼 짧은 시간만에 이동할 수 있다. 하지만, 치안을 유지하기 위해서 플로우 내에 제국군을 주둔시켜야 한다.

모든 행성 간에 플로우를 설치하고 플로우 내에 제국군을 주둔하면, 제국의 제정이 악화되기 때문에 황제 윤석이는 제국의 모든 행성을 연결하면서 플로우 관리 비용을 최소한으로 하려 한다.

N개의 행성은 정수 1,…,N으로 표시하고, 행성 i와 행성 j사이의 플로우 관리비용은 Cij이며, i = j인 경우 항상 0이다.

제국의 참모인 당신은 제국의 황제 윤석이를 도와 제국 내 모든 행성을 연결하고, 그 유지비용을 최소화하자. 이때 플로우의 설치비용은 무시하기로 한다.

입력

입력으로 첫 줄에 행성의 수 N (1 ≤ N ≤ 1000)이 주어진다.

두 번째 줄부터 N+1줄까지 각 행성간의 플로우 관리 비용이 N x N 행렬 (Cij), (1 ≤ i, j ≤ N, 1 ≤ Cij ≤ 100,000,000, Cij = Cji, Cii = 0) 로 주어진다.

출력

모든 행성을 연결했을 때, 최소 플로우의 관리비용을 출력한다.

💚나의 풀이

• 정답 출력할 때 주의해야 할 게 데이터 크기가 100,000,000 으로 매우 크기 때문에 long 타입으로 선언해서 출력해야 맞는다.
• 인접행렬로 들어오는 각 i→ j로의 비용을 pQ에 Edge 형태로 중복되지 않게 담아야 했다.
• 왜냐하면 최소 신장 트리는 ‘무방향’ 정점이 N-1개의 간선으로 이루어진 최소 가중치 트리 이기 때문에 중복되지 않도록 행렬 속 i<j인 부분에서 얻은 비용들을 pQ에 차례로 담았다.
• useEdge가 N-1개 되기 전까지 현재 이을 간선이 사이클 형성 하지만 않는 다면 결합시키면서 useCost를 누적시키다가. while문을 탈출하면 그 값을 출력하도록 문제를 풀었.

package to_0906_C;

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

/*16398번. 행성 연결- 최소비용신장트리 문풀 */
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 N;
	static int[][] map;
	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();
		//행렬에 입력 받을 건데 
		parent = new int[N+1];
		for(int i=1; i<=N; i++) parent[i]= i;//자기 자신으로 세팅 
		
		//얘네들 중 i>j 인 값에 대하여서만 간선으로 담기 
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		
		map = new int[N+1][N+1];
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				map[i][j] = kb.nextInt();
				if(i<j) pQ.offer(new Edge(i, j, map[i][j]));
			}
		}
		//최소비용 신장트리 시작 
		int useEdge= 0;
		//##############주의 데이터 크기 크니까 답은 long타입으로 선언해서 써야 한다. !!!!!
		long useCost = 0; // 100,000,000 이므로 long형
		while(useEdge<N-1) {
			Edge cur = pQ.poll();
			//사이클 형성하지 않는 애만 이어붙임 
			if(find(cur.s) != find(cur.e)) {
				union(cur.s, cur.e);
				useCost += cur.val;
				useEdge++;
			}
		}
		System.out.println(useCost);
	}
}