[백준/JAVA] 1197_최소 스패닝 트리

백준🔗

1197번: 최소 스패닝 트리

 

문제

 

 

간단 풀이

최소 스패닝 트리(최소 비용 신장 트리, MST)를 구하는 알고리즘으로 대표적으로 2가지가 있다.

 

1. 크루스칼(KRUSKAL)

: '간선'을 하나씩 선택해서 MST를 찾는 알고리즘

1) 모든 간선을 가중치에 따라 오름차순으로 정렬한다.

2) 가중치가 가장 낮은 '간선'부터 선택하면서 트리를 증가시킨다.

    선택된 간선의 양 끝 노드는 union해서 같은 집합으로 묶는다.

    이 때, 사이클이 존재하면 그 다음으로 가중치가 낮은 간선을 선택한다.

    (선택된 간선의 양 끝 노드가 이미 같은 집합에 있는 경우 사이클이라고 판단)

3) (노드 개수-1)개의 간선이 선택될 때까지 2번 과정을 반복한다.

 

2. 프림(Prim)

: 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식

0) 우선순위 큐가 아닌 반복문을 사용하는 경우, dist(1차원 배열)를 전부 무한대로 초기화 해준다.

1) 임의의 정점을 하나 선택해서 시작한다.

2) 선택한 정점과 인접한 정점들 중 최소 비용의 간선이 존재하는 '정점'을 선택한다.

3) 모든 정점이 선택될 때까지 2번 과정을 반복한다.

 

크로스칼 vs 프림 차이점!

크로스칼은 최소 비용의 '간선'을 선택하는 것이고,
프림은 최소 비용의 간선이 존재하는 '정점'을 선택하는 것!!

 

 

이 중 이번 문제는 크루스칼을 적용해서 풀었다.

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int[] p; // 집합의 대표 저장하는 배열

	public static void main(String[] args) throws Exception {
		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()); // 간선 개수

		// 크루스칼 1단계 : 간선을 정렬한다. (오름차순)
		PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				return o1.w - o2.w; // 가중치 기준 오름차순 정렬
			}
		});
		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 C = Integer.parseInt(st.nextToken()); // 가중치
			pq.add(new Edge(A, B, C));
		}

		// 크루스칼 2단계 : V-1개의 간선을 뽑는데, 사이클이 발생 안 하는 애들만!!
		// 사이클 판단은 unionfind~ 같은 집합이라면 사이클 발생
		p = new int[V + 1];
		for (int i = 1; i <= V; i++) {
			p[i] = i;
		}

		int W = 0;
		while (!pq.isEmpty()) {
			Edge cur = pq.poll();
			if (findSet(cur.n1) == findSet(cur.n2)) { // 사이클 발생
				continue;
			}
			union(cur.n1, cur.n2); // 이어주기
			W += cur.w;
		}
		System.out.println(W);
	}

	static class Edge {
		int n1, n2, w; // 정점, 가중치

		public Edge(int n1, int n2, int w) {
			this.n1 = n1;
			this.n2 = n2;
			this.w = w;
		}
	}

	static int findSet(int x) {
		if (x != p[x]) {
			p[x] = findSet(p[x]);
		}
		return p[x];
	}

	static void union(int x, int y) {
		p[findSet(y)] = findSet(x);
	}
}

 

참고 자료