[백준] 1647. 도시 분할 계획 (JAVA, MST, 크루스칼)

www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

두 개의 마을로 나눈다고 SUBSET하고 뻘짓하다가 시간초과났다 ㅎ

일 단 MST로 연결하되, 모든 정점을 연결한 상황에서 가장 가중치가 큰 길 하나만 없애면

자동으로 두 마을로 나뉘게 된다.

 

즉 간선을 하나 없앤다 => 간선 개수가 N-2개가 될 때까지만 UNION-FIND해준다.

import java.util.Arrays;
import java.util.Scanner;

class House implements Comparable<House>{
	int cur;
	int next;
	int cost;
	public House(int cur,int next, int cost) {
		super();
		this.cur=cur;
		this.next=next;
		this.cost = cost;
	}
	@Override
	public int compareTo(House o) {
		return this.cost-o.cost;
	}
	@Override
	public String toString() {
		return "House [cur=" + cur + ", next=" + next + ", cost=" + cost + "]";
	}
	
}

public class Main {
	static int n,m;
	static House[] list;
	static int[] parent;
	static int answer;
	static int cnt;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		list=new House[m];
		for (int i = 0; i < m; i++) {
			list[i]=new House(sc.nextInt(),sc.nextInt(),sc.nextInt());
		}
		parent=new int[n+1];
		for (int i = 1; i <=n; i++) {
			parent[i]=i;
		}
		Arrays.sort(list);
		for(House h:list) {
			union(h.cur,h.next,h.cost);
			if(cnt==n-2)break;
		}
		System.out.println(answer);
	}
	
	private static int find(int x) {
		if(x==parent[x])return x;
		return parent[x]=find(parent[x]);
	}
	private static void union(int cur, int next, int cost) {
		cur=find(cur);
		next=find(next);
		if(cur!=next) {
			answer+=cost;
			cnt+=1;
			if(cur<next) {
				parent[cur]=next;
			}else {
				parent[next]=cur;
			}
		}
	}
}