백준 1197: 최소 스패닝 트리

문제 요약

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

문제 분류

• 그래프 이론
• 최소 스패닝 트리

문제 풀이

최소 스패닝 트리를 구축하는 문제이다. 프림 알고리즘과 크루스칼의 두 알고리즘을 이용해서 풀었다.
프림 알고리즘은 임의의 정점으로부터 항상 적은 가중치로 다른 정점을 방문하여 추가하는 알고리즘이다.
크루스칼 알고리즘은 간선의 가중치가 낮은 간선의 정점들을 트리 집합에 추가하며 최소 스패닝 트리를 구축하는 방법이다.

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

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

public class Main {
	static ArrayList<Node>[] edge;
	static boolean visited[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
		int cnt, v, u, c, res = 0;
		Node node;
		PriorityQueue<Node> pq = new PriorityQueue<>();
		edge = new ArrayList[n + 1];
		visited = new boolean[n + 1];
		for(int i = 1; i <= n; i++)
			edge[i] = new ArrayList<>();
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			v = Integer.parseInt(st.nextToken());
			u = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			edge[v].add(new Node(u, c));
			edge[u].add(new Node(v, c));
		}
		for(Node e : edge[1])
			pq.offer(e);
		visited[1] = true;
		cnt = 1;
		while(!pq.isEmpty()) {
			node = pq.poll();
			if(visited[node.idx]) continue;
			visited[node.idx] = true;
			res += node.w;
			cnt++;
			if(cnt == n) break;
			for(Node e : edge[node.idx]) {
				if(!visited[e.idx])
					pq.offer(e);
			}
		}
		System.out.println(res);
	}
}

class Node implements Comparable<Node> {
	int idx;
	int w;
	public Node(int idx, int w) {
		this.idx = idx;
		this.w = w;
	}
	@Override
	public int compareTo(Node o) {
		return Integer.compare(this.w, o.w);
	}
}

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

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

public class Main {
	static int p[];
	
	static int find(int a) {
		if(p[a] == 0) return a;
		return p[a] = find(p[a]);
	}
	
	static void merge(int a, int b) {
		a = find(a);
		b = find(b);
		if(a == b) return;
		p[a] = b;
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
		int v, u, c, res = 0;
		Node node;
		PriorityQueue<Node> pq = new PriorityQueue<>();
		p = new int[n + 1];
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			v = Integer.parseInt(st.nextToken());
			u = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			pq.offer(new Node(v, u, c));
		}
		int cnt = 1;
		while(!pq.isEmpty()) {
			node = pq.poll();
			if(find(node.a) == find(node.b)) continue;
			merge(node.a, node.b);
			res += node.w;
			cnt++;
			if(cnt == n) break;
		}
		System.out.println(res);
	}
}

class Node implements Comparable<Node> {
	int a;
	int b;
	int w;
	public Node(int a, int b, int w) {
		this.a = a;
		this.b = b;
		this.w = w;
	}
	@Override
	public int compareTo(Node o) {
		return Integer.compare(this.w, o.w);
	}
}