[BOJ] 백준 1197번 최소 스패닝 트리 (Java)

#1197 최소 스패닝 트리

난이도 : 골드 4

유형 : 그래프 / 최소 스패닝 트리 / 프림  알고리즘 / 크루스칼 알고리즘

1197번: 최소 스패닝 트리

▸ 문제

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

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

▸ 입력

첫째 줄에 정점의 개수 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보다 작거나 같은 데이터만 입력으로 주어진다.

▸ 출력

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

 

문제 풀이  

최소 스패닝 트리의 문제로 공부를 위해 프림과 크루스칼을 각각 사용해서 풀이를 해보았다. 크루스칼, 프림 공부하러가기

📚 조건

• 정점의 개수 V (1 <= V <= 10,000)
• 간선의 개수 E (1<= E <= 100,000)
• 간선 가중치 value  ( |value| <= 1,000,000)

 크루스칼 알고리즘은 간선 위주로 탐색을 진행하고 프림 알고리즘은 정점 위주로 탐색을 진행한다. 간선의 개수가 적은 경우 크루스칼이 더 용이하며 많은 경우 정점 위주 탐색인 프림이 더 용이하다. 둘 다 시간복잡도는 O(ElogV)로 같다.

 

 

풀이 코드 (프림 알고리즘) 

import java.io.*;
import java.util.*;

public class Main {
	static int total;
	static List<Node>[] list;
	static boolean[] visited;
	static class Node implements Comparable<Node>{
		int to;
		int value;
		
		public Node(int to, int value) {
			this.to = to;
			this.value = value;
		}

		@Override
		public int compareTo(Node o) {
			return this.value - o.value;
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int v = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[v+1];
		visited = new boolean[v+1];
		for(int i=1; i<v+1; i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int i=0; i<e; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			list[a].add(new Node(b,w));
			list[b].add(new Node(a,w));
		}
		
		prim(1);
		System.out.println(total);
	}
	
	static void prim(int start) {
		Queue<Node> pq = new PriorityQueue<>();
		
		pq.add(new Node(start,0));
		while(!pq.isEmpty()) {
			Node p = pq.poll();
			int node = p.to;
			int weight = p.value;
			
			if(visited[node]) continue;
			// 선택한 간선의 정점으로부터 가장 낮은 가중치 갖는 정점 선택 
			visited[node]= true;
			total += weight;
			
			for(Node next : list[node]) {
				if(!visited[next.to]) {
					pq.add(next);
				}
			}
		}
		
	}
}

 

풀이 코드 (크루스칼 알고리즘)

import java.io.*;
import java.util.*;

public class Main {

	static int total;
	static int[] parent;
	static class Node implements Comparable<Node>{
		int to;
		int from;
		int value;
		
		public Node(int to, int from, int value) {
			this.to = to;
			this.from = from;
			this.value = value;
		}

		@Override
		public int compareTo(Node o) {
			return this.value - o.value;
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int v = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());
		
		parent = new int[v+1];
		for(int i=1; i<v+1; i++) {
			parent[i] = i;
		}
		
		Queue<Node> pq = new PriorityQueue<>();
		for(int i=0; i<e; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			pq.add(new Node(a,b,w));
		}
		
		int size = pq.size();
		int total = 0;
		for(int i=0; i<size; i++) {
			Node node = pq.poll();
			int to = find(node.to);
			int from = find(node.from);
			
			if(!isSameParent(to,from)) {
				total += node.value;
				union(node.to, node.from);
			}
		}
		System.out.println(total);
	}
	public static int find(int x) {
		if(parent[x] ==x ) return x;
		return parent[x] = find(parent[x]);
	}
	
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		if(x!= y) {
			parent[y] =x;
		}
	}
	
	public static boolean isSameParent(int x, int y ) {
		x = find(x);
		y = find(y);
		if(x==y) return true;
		else return false;
	}
}

 

프림 알고리즘 결과

크루스칼 알고리즘 결과

→ 프림과 크루스칼의 성능 차이는 크게 안나는 것을 확인할 수 있다.