[백준] 1197번: 최소 스패닝 트리 Java

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

 

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

 

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

 

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

1197번: 최소 스패닝 트리

접근

최소 신장 트리(MST, Minimum Spanning Tree) 문제이다.

신장트리(스피닝 트리)란 여러개의 간선 중 일부 간선만을 선택해 트리를 구성하는 것으로,

최소 신장 트리는 간선 간의 가중치의 합이 가장 적은 신장 트리이다.

 

이를 정리하면 3가지 조건을 가져야 한다.

1) 간선의 가중치의 합이 최소이어야 한다. (최소 신장 트리)

2) 간선의 개수는 n-1이어야 한다. (최소 신장 트리)

3) 싸이클이 존재하지 않아야 한다. (최소 신장 트리)

 

이를 해결하는 방법은 크게 2가지 알고리즘 방법이 존재한다.

 

1. Kruskal MST 알고리즘

2. Prim MST 알고리즘

 

이 중 Kruskal MST 알고리즘 방법으로 문제를 해결할 예정이다.

(다른 문제에서 Prim MST 알고리즘은 설명할 예정)

 

Kruskal MST 알고리즘은 일종의 그리디 알고리즘이다.

1) 간선의 정보를 가중치가 적은 순으로 정렬한다.

2) 정렬한 간선 정보에 대해 연결된 노드의 부모를 비교한다.

 2-1) 만약 두 노드가 부모가 다르다면 부모를 재설정한 뒤, 해당 간선을 선택한다.

 2-2) 만약 두 노드의 부모가 같다면 해당 간선은 선택하지 않는다.

 

자세한 설명은 아래 사이트를 참고하였다.

https://sskl660.tistory.com/72

[Java]크루스칼 알고리즘(Kruskal Algorithm)

 

부모 노드를 찾고 세팅해야 함으로 필연적으로 유니온 파인드 알고리즘이 필요하다.

 

구현

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

public class Main {
	//https://www.acmicpc.net/problem/1197
	
	static List<int[]> NodeList;
	static int[] Parents;
	static int V;
	
	//부모 찾기
	public static int getParent(int node) {
		if(Parents[node]==node) return node;
		return Parents[node]=getParent(Parents[node]);
	}
	//부모 세팅, 작은 수가 부모
	public static void setParent(int node1, int node2) {
		int p1 = getParent(node1);
		int p2 = getParent(node2);
		if(p1<p2) Parents[p2]=p1;
		else Parents[p1]=p2;
	}
	//같은 부모 판별
	public static boolean isSameParent(int node1, int node2) {
		//다른 부모라면 부모 세팅 후 false 리턴
		if(getParent(node1)!=getParent(node2)) {
			setParent(node1, node2);
			return false;
		}
		//같은 부모라면 true 리턴
		return true;
	}
	//크루스칼 알고리즘 사용
	public static int kruskal() {
		//간선 비용이 적은 순으로 정렬
		Collections.sort(NodeList, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[2]<o2[2]) return -1;
				else if(o1[2]>o2[2]) return 1;
				return 0;
			}
		});
		//선택한 간선의 개수
		int count = 0;
		int sum = 0;
		//탐색
		for(int[] edgeInfo:NodeList) {
			//모든 간선을 선택했다면 종료(트리의 간선 수 = n-1)
			if(count==V-1) break;
			int node1 = edgeInfo[0];
			int node2 = edgeInfo[1];
			int cost = edgeInfo[2];
			//다른 부모라면 간선 선택
			if(!isSameParent(node1, node2)) {
				//간선 개수 증가 및 비용 합계
				count++;
				sum+=cost;
			}
		}
		//비용 합계 출력
		return sum;
	}
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		V=Integer.parseInt(st.nextToken()); //정점 개수
		int e=Integer.parseInt(st.nextToken()); //간선 개수
		int a=-1, b=-1, c=-1;
		Parents=new int[V+1];
		NodeList = new ArrayList<>();
		for(int i=1;i<=V;i++) {
			Parents[i]=i;
		}
		
		for(int i=0;i<e;i++) {
			st=new StringTokenizer(br.readLine());
			a=Integer.parseInt(st.nextToken()); //노드1
			b=Integer.parseInt(st.nextToken()); //노드2
			c=Integer.parseInt(st.nextToken()); //가중치
			NodeList.add(new int[] {a,b,c});
		}
		System.out.println(kruskal());
		br.close();
	}
}