[백준] 21924: 도시 건설 - 최소신장트리(Minimum Spanning Tree, MST) + 크루스칼(Kruskal) JAVA

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

21924번: 도시 건설

코드설명

전형적인 크루스칼 알고리즘입니다.

 

 

다만, 한가지 유의해야할점은

-  만약 모든 건물이 연결되어 있지 않는다면 -1을 출력한다.

모든 건물이 연결되어있다면, findParent를 진행하였을때 모두 같은 집합에 속해야만 합니다. (문제에서 가장 중요한점 )

for(int i=1;i<N;i++) {
    if( findParent(i) != findParent(i+1)) {
        System.out.println("-1");
        return ;
    }
}

 

unionFind 알고리즘에 의하여 각 노드의 parent가 업데이트 되지 않는 경우가 있기에

모든 노드를 돌면서 findParent를 통해서 parent를 직접 다시 한번 체크해줘야합니다.

코드

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,M;
	public static int[] parent = new int[100001];
	public static ArrayList<Edge> edges = new ArrayList<>();
	public static long result = 0;
	public static long wholecost = 0;
	public static int count = 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());
    	M = Integer.parseInt(st.nextToken());
    	
    	for(int i=0;i<=N;i++) {
    		parent[i] = i;
    	}
    	
    	for(int j=0;j<M;j++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		int cost = Integer.parseInt(st.nextToken());
    		edges.add(new Edge(a, b, cost));
    		wholecost += 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;
    		}
    	}
//    	for(int i=0;i<=N;i++) {
//    		System.out.println("FINDPARENT"+parent[i]);
//    	}    	
    	for(int i=1;i<N;i++) {
    		if( findParent(i) != findParent(i+1)) {
    			System.out.println("-1");
    			return ;
    		}
    	}
    	
    	if(wholecost - result < 0) {
    		System.out.println("0");
    	}else {
    		System.out.println(wholecost - 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,M;
	public static int[] parent = new int[100001];
	public static ArrayList<Edge> edges = new ArrayList<>();
	public static long result = 0;
	public static long wholecost = 0;
	public static int count = 0;
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	N = sc.nextInt();
    	M = sc.nextInt();
    	
    	for(int i=0;i<=N;i++) {
    		parent[i] = i;
    	}
    	
    	for(int j=0;j<M;j++) {
    		int a = sc.nextInt();
    		int b = sc.nextInt();
    		int cost = sc.nextInt();
    		edges.add(new Edge(a, b, cost));
    		wholecost += 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;
    		}
    	}
//    	for(int i=0;i<=N;i++) {
//    		System.out.println("FINDPARENT"+parent[i]);
//    	}    	
    	for(int i=1;i<N;i++) {
    		if( findParent(i) != findParent(i+1)) {
    			System.out.println("-1");
    			return ;
    		}
    	}
    	
    	if(wholecost - result < 0) {
    		System.out.println("0");
    	}else {
    		System.out.println(wholecost - result);	
    	}
    	
    	
    }
    
    public static int findParent(int x) {
    	if( x == parent[x]) return x;
    	return parent[x] = findParent(parent[x]);
    }
    
    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;
		}else {
			return 0;
		}
	}
}