크루스칼(kruskal) 알고리즘

크루스칼 알고리즘은 최소신장트리를 만드는 문제이다. 

신장트리는 모든 정점(Vertex)이 간선(Edge)로 이어진 그래프이다. 굳이 영어를 끼워넣은 것은 내가 헷깔려서 그렇다. 

 

모든 정점을 잇는 간선의 값을 최소한으로 해서 연결하면 그게 최소신장 트리가 되고 이것을 만드는 것이 크루스칼 알고리즘이다. 

크루스칼 알고리즘에는 서로소 집합을 구현해야 한다. 서로소 집합은 각 정점끼리 부모를 찾아주는 집합으로 

보통 Union-Find함수로 많이 구현한다.  

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

1197번: 최소 스패닝 트리

 

 

 

package practice2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;

class info implements Comparable<info> {
	int from, to, weight;

	public info(int from, int to, int weight) {
		this.from = from;
		this.to = to;
		this.weight = weight;
	}

	@Override
	public int compareTo(info o) {
		return Integer.compare(this.weight, o.weight);
	}

	
}

public class boj1197 {
	static int N, M, answer;
	static int parent[];
	static ArrayList<info> list;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] s = in.readLine().split(" ");
		N = Integer.parseInt(s[0]);
		M = Integer.parseInt(s[1]);
		
		list = new ArrayList<>();

		for (int i = 0; i < M; i++) {
			s = in.readLine().split(" ");
			int from = Integer.parseInt(s[0]);
			int to = Integer.parseInt(s[1]);
			int weight = Integer.parseInt(s[2]);
			list.add(new info(from, to, weight));
		}
		Collections.sort(list);
		
		parent = new int[N+1];
		for(int i =1; i<=N;i++)parent[i]=i;
		int cnt =0;
		for(int i =0; i<M;i++) {
			int from = list.get(i).from;
			int to = list.get(i).to;
			int weight = list.get(i).weight;
			if(Find(from)!=Find(to)) {
				Union(from,to);
				answer +=weight;
				cnt++;
			}
			if(cnt==M-1)break;//시간을 조금이라도 줄이기 위해서
		}
		System.out.println(answer);
	}

	private static void Union(int x, int y) {
		x = Find(x);
		y = Find(y);
		if(x!=y)
			parent[y]=x;
	}

	private static int Find(int x) {
		if (x == parent[x])
			return x;
		else
			return parent[x] = Find(parent[x]);
	}
}

 

우선 인접 리스트를 만들어서 간선들의 시작정점과 끝 정점을 넣어준다. 그리고 인접리스트를 거리 순으로 정렬해주고 

파인드함수로 시작 정점과 끝 정점이 사이클이 발생하는지 안하는지 확인하고 안하면 그 간선을 신장트리에 추가한다.