[백준 1197] 최소 스패닝 트리 (Prim, Kruskal) (JAVA)

문제 링크: https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

1. 주의할 점

- MST의 알고리즘으로는 프림이나 크루스칼이 존재하는데 둘중 하나로 풀면 된다

- 간선의 개수 적으면 크루스칼이 빨리되고 정점의 개수가 적다면 프림이 빨리 된다

 

2. 구현

 

[Prim]

- 각 Node의 간선들을 Li[]배열에 모두 담는다

- 정점 1부터 시작하며, Deque에 담고 시작한다 -> Deque에는 항상 최대 1개의 Node만 가질 예정

- Deque에서 정점을 빼며, 각 정점에 연결된 모든 간선들중, 방문하지 않은 Node와 연결된 간선의 경우 우선순위큐에 삽입한다

- 우선순위큐가 빌때까지 최소의 가중치를 가지며 방문하지 않은 Node와 연결되는 경우, 다음 Node를 Deque에 삽입하고 하던 과정을 멈춘다

- 위의 과정을 반복한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_bj_1197_최소스패닝트리 {
	static class Info implements Comparable<Info>{
		int idx;
		long val;
		public Info(int idx, long val) {
			this.idx = idx;
			this.val = val;
		}
		@Override
		public int compareTo(Info o) {		
			return Long.compare(this.val, o.val);
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);
		int node = Integer.parseInt(st.nextToken());
		int edge = Integer.parseInt(st.nextToken());
		boolean visit[] = new boolean[node+1];
		List<Info> li[];
		li = new List[node+1];
		for(int i=1;i<=node;i++)
			li[i] = new ArrayList<>();
		
		for(int i=0;i<edge;i++) {
			String str = br.readLine();
			StringTokenizer st2 = new StringTokenizer(str);
			int start = Integer.parseInt(st2.nextToken());
			int target = Integer.parseInt(st2.nextToken());
			long val = Integer.parseInt(st2.nextToken());
			li[start].add(new Info(target,val));
			li[target].add(new Info(start,val));
		}
		long result=0;
		PriorityQueue<Info> pq = new PriorityQueue<>();
		Deque<Integer> dq = new ArrayDeque<>(); 
		dq.offer(1);
		while(!dq.isEmpty()) {
			int cidx = dq.poll();
			visit[cidx]=true;
			for(int i=0;i<li[cidx].size();i++) {
				int next = li[cidx].get(i).idx;
				long nv = li[cidx].get(i).val;
				if(!visit[next]) {
					pq.offer(new Info(next,nv));
				}
			}
			while(!pq.isEmpty()) {
				int next = pq.peek().idx;
				long nv = pq.peek().val;
				pq.poll();
				if(!visit[next]) {
					visit[next]=true;
					dq.add(next);
					result+=nv;
					break;
				}
			}		
		}
		System.out.println(result);
	}
}

 

[Kruskal]

- 간선의 가중치가 작은거부터 확인

- 만약 새로 추가하는 Node가 같은 집합이 아닐 경우 새로 추가(즉, Cycle이 생성되지 않도록 한다) 

- 위의 과정을 모든 Node를 탐색할때까지 반복

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

public class Main_bj_1197_최소스패닝트리_kruskal {
	static class Info implements Comparable<Info>{
		int start,target;
		long val;
		public Info(int start,int target, long val) {
			this.start = start;
			this.target = target;
			this.val = val;
		}
		@Override
		public int compareTo(Info o) {		
			return Long.compare(this.val, o.val);
		}
	}
	
	public static int parent(int idx) {
		if (root[idx] == idx)
			return idx;
		return root[idx] = parent(root[idx]);
	}

	public static void make_union(int a, int b) {
		a = parent(a);
		b = parent(b);
		if(a<b) root[b]=a;
		else root[a]=b;
	}

	public static int find(int a, int b) {
		a = parent(a);
		b = parent(b);
		if(a==b) return 1;
		else return 0;
	}
	
	static int root[];
	static List<Info> li;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);
		int node = Integer.parseInt(st.nextToken());
		int edge = Integer.parseInt(st.nextToken());
		boolean visit[] = new boolean[node+1];
		
		li = new ArrayList<Info>();		
		root = new int[node + 1];
		for (int i = 1; i <= node; i++)
			root[i] = i;
		
		for(int i=0;i<edge;i++) {
			String str = br.readLine();
			StringTokenizer st2 = new StringTokenizer(str);
			int start = Integer.parseInt(st2.nextToken());
			int target = Integer.parseInt(st2.nextToken());
			long val = Integer.parseInt(st2.nextToken());
			li.add(new Info(start,target,val));
		}
		Collections.sort(li);
		int cnt = 0;
		long result = 0;
		while (cnt < li.size()) {
			int start = li.get(cnt).start;
			int end = li.get(cnt).target;
			int res = find(start,end);
			if (res==1) { 
				cnt++;
				continue;
			}
			make_union(start,end);
			result += li.get(cnt).val;
			cnt++;
		}
		System.out.println(result);
	}
}