MST 최소신장트리

25 Jun 2020

Reading time ~2 minutes

MST (Minimum Spanning Tree) 최소 신장 트리

사이클 없이 최소의 비용(가중치)으로 모든 노드(정점)을 방문하는 트리
Kruskal , Prim 알고리즘으로 구현 가능( Kruskal은 간선 Prim은 정점선택을 기반으로하는 )

문제 : 백준 1197

KeyPoint

Comparable 사용 정렬 기준을 가중치로 설정
우선순위큐 사용하여 자동 정렬
Kruskal 알고리즘 이용시 Find 함수에서 트리의 레벨을 2단계로…(하지 않으면 백준에서 시간초과 발생)

Kruskal 알고리즘

사이클이 형성되지 않는 최소 비용의 간선을 선택하는 방식
Find, Union 함수를 구현하여 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class S_1197_2 {

	
	static int parents[];
	
	static class E implements Comparable<E>{
		int st,ed,val;

		public E(int st, int ed, int val) {
			super();
			this.st = st;
			this.ed = ed;
			this.val = val;
		}

		@Override
		public int compareTo(E o) {
			// TODO Auto-generated method stub
			return this.val - o.val;
		}
		
		
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		int V = Integer.parseInt(stk.nextToken());
		int E = Integer.parseInt(stk.nextToken());
		
		PriorityQueue<E> pq = new PriorityQueue<E>();
		
		for (int i = 0; i < E; i++) {
			stk = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(stk.nextToken())-1;
			int B = Integer.parseInt(stk.nextToken())-1;
			int C = Integer.parseInt(stk.nextToken());
			pq.add(new E(A,B,C));
		}
		
		
		
		int result=0;
		parents = new int[V];
		for (int i = 0; i < V; i++) {
			parents[i] = i;
		}
		
		for (int i = 0; i < E; i++) {
			E edge = pq.poll();
			if(find(edge.st) == find(edge.ed))
				continue;
			result+=edge.val;
			union(edge.st,edge.ed);
		}
		
		System.out.println(result);
	}

	private static int find(int st) {
		// TODO Auto-generated method stub
			if(st==parents[st])
				return st;
			parents[st]=find(parents[st]);
			return parents[st];
	}

	private static void union(int st, int ed) {
		// TODO Auto-generated method stub
		parents[find(st)]=find(ed);
	}
}

Prim 알고리즘

사이클이 형성되지 않는 최소 비용의 을 선택하는 방식
이전 단계에서 트리를 확장해 나가는 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class S_1197 {

	static class Vertex implements Comparable<Vertex>{
		int v,val;

		public Vertex(int v, int val) {
			super();
			this.v = v;
			this.val = val;
		}

		@Override
		public int compareTo(Vertex v) {
			// TODO Auto-generated method stub
			return this.val-v.val;
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		int V = Integer.parseInt(stk.nextToken());
		int E = Integer.parseInt(stk.nextToken());
		
		ArrayList<Vertex>[] arr = new ArrayList[V];
		
		for (int i = 0; i < V; i++) {
			arr[i]=new ArrayList<>();
		}
		
		for (int i = 0; i < E; i++) {
			stk = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(stk.nextToken())-1;
			int B = Integer.parseInt(stk.nextToken())-1;
			int C = Integer.parseInt(stk.nextToken());
			arr[A].add(new Vertex(B, C));
			arr[B].add(new Vertex(A, C));
		}
		
		PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>();
		pq.addAll(arr[0]);
		boolean[] visited = new boolean[V];
		visited[0]=true;
		
		int result = 0;
		
		for (int i = 0; i < V-1; i++) {
			while(true) {
				Vertex tmp = pq.poll();
				if(visited[tmp.v])
					continue;
				visited[tmp.v]=true;
				result+=tmp.val;
				pq.addAll(arr[tmp.v]);
				break;
			}
		}
		
		System.out.println(result);
	}

}

Reference

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html