[백준] 16398: 행성 연결 - 최소신장트리(Minimum Spanning Tree, MST) + 크루스칼(Kruskal) JAVA

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

16398번: 행성 연결

코드설명

최소신장트리(Minimum Spanning Tree, MST) + 크루스칼(Kruskal)를 활용하는 문제입니다.

 

다만, 

문제 조건에 보면

각 행성간의 플로우 관리 비용이 N x N 행렬 (Cij), (1 ≤ i, j ≤ N, 1 ≤ Cij ≤ 100,000,000, Cij = Cji, Cii = 0) 

 

최악의 상황을 가정하면, 만약 N이 1000이고, 각 모든 비용이 100,000,000  이라면, 최소비용을 구한다고하였을때 

1000 * 100,000,000 = 100,000,000,000(1000억) 입니다.

1000 억은 int 범위를 벗어나므로 long으로 선언합니다.

 

또한 시간을 줄일 수 있는 방법으로, 행렬에 대한 처리가 있습니다.

for(int i=1;i<=N;i++) {
    st = new StringTokenizer(br.readLine());
    for(int j=1;j<=i;j++) {
        int cost = Integer.parseInt(st.nextToken());
        if(i == j) continue;
        edges.add(new Edge(i, j, cost));
    }
}

위의 코드처럼 j<=i 까지 처리합니다. 처음에는 j<=N 까지 처리하여 같은 간선을 2번 처리했습니다.

 

코드

BufferedReader와 행렬상에서 최적화 진행한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

	public static int N;
	public static int[] parent = new int[1001];
	public static ArrayList<Edge> edges = new ArrayList<>();
	public static long result = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N= Integer.parseInt(st.nextToken());
    	
    	for(int i=0;i<=N;i++) {
    		parent[i] = i;
    	}
    	
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=1;j<=i;j++) {
    			int cost = Integer.parseInt(st.nextToken());
    			if(i == j) continue;
    			edges.add(new Edge(i, j, cost));
    		}
    	}
    
    	Collections.sort(edges);
    	
    	
    	for(int i=0;i<edges.size();i++) {
    		int a = edges.get(i).nodeA;
    		int b = edges.get(i).nodeB;
    		int cost = edges.get(i).distance;
    		if( findParent(a) != findParent(b) ) {
    			unionParent(a, b);
    			result += cost;
    			
    		}
    		
    	}
    	System.out.println(result);
    }
    
    //부모를 찾는다.
    public static int findParent(int a) {
    	if( a == parent[a]) return a;
    	return parent[a] = findParent(parent[a]);
    }
    
    //
    public static void unionParent(int a, int b) {
    	a = findParent(a);
    	b = findParent(b);
    	if( a < b ) parent[b] = a;
    	else parent[a] = b;
    }
    
    
   
    
    
}

class Edge implements Comparable<Edge>{
	int nodeA;
	int nodeB;
	int distance;
	
	public Edge(int nodeA, int nodeB, int distance) {
		this.nodeA = nodeA;
		this.nodeB = nodeB;
		this.distance = distance;
	}
	//비용이 낮은것으로 정렬합니다.
	@Override
	public int compareTo(Edge other) {
		if(this.distance > other.distance) {
			return 1;
		}else if(this.distance < other.distance) {
			return -1;
		}
		return 0;
	}
}

 

import java.util.*;



public class Main {

	public static int N;
	public static int[] parent = new int[1001];
	public static ArrayList<Edge> edges = new ArrayList<>();
	public static long result = 0;
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	N=sc.nextInt();
    	
    	for(int i=0;i<=N;i++) {
    		parent[i] = i;
    	}
    	
    	for(int i=1;i<=N;i++) {
    		for(int j=1;j<=N;j++) {
    			int cost = sc.nextInt();
    			if(i == j) continue;
    			edges.add(new Edge(i, j, cost));
    		}
    	}
    
    	Collections.sort(edges);
    	
    	
    	for(int i=0;i<edges.size();i++) {
    		int a = edges.get(i).nodeA;
    		int b = edges.get(i).nodeB;
    		int cost = edges.get(i).distance;
    		if( findParent(a) != findParent(b) ) {
    			unionParent(a, b);
    			result += cost;
    			
    		}
    		
    	}
    	System.out.println(result);
    }
    
    //부모를 찾는다.
    public static int findParent(int a) {
    	if( a == parent[a]) return a;
    	return parent[a] = findParent(parent[a]);
    }
    
    //
    public static void unionParent(int a, int b) {
    	a = findParent(a);
    	b = findParent(b);
    	if( a < b ) parent[b] = a;
    	else parent[a] = b;
    }
    
    
   
    
    
}

class Edge implements Comparable<Edge>{
	int nodeA;
	int nodeB;
	int distance;
	
	public Edge(int nodeA, int nodeB, int distance) {
		this.nodeA = nodeA;
		this.nodeB = nodeB;
		this.distance = distance;
	}
	//비용이 낮은것으로 정렬합니다.
	@Override
	public int compareTo(Edge other) {
		if(this.distance > other.distance) {
			return 1;
		}else if(this.distance < other.distance) {
			return -1;
		}
		return 0;
	}
}