(백준) – 1197 최소 스패닝 트리 문제 해결 – Java

  • by

https://www.acmicpc.net/problem/1197

1197: 최소 스패닝 트리

첫 번째 행에는 정점 수 V(1≤V≤10,000)와 간선 수 E(1≤E≤100,000)가 주어집니다.

다음 E 행에는 각 간선의 정보를 나타내는 3개의 정수 A, B, C가 주어집니다.

이것은 A번 정점과 B번 정점

www.acmicpc.net

인기글

최소 스패닝 트리(MST)란?

모든 정점을 연결하는 가중치의 합이 최소가 되는 트리로, MST라고 부른다.

즉, 양방향(무향) 가중 글리프로 각 정점 사이의 최소 비용의 경로를 구하여 모든 정점을 연결할 수 있다.

MST를 해결하기 위해 KRUSKAL 알고리즘과 PRIM 알고리즘이 있습니다.

KRUSAKL 알고리즘

간선을 하나씩 탐색하고 MST를 찾는 알고리즘이다.

대응하는 알고리즘에서는, 서로의 세트에 사용되는 유니온 find 가 사용됩니다.

모든 간선을 가중 기준으로 오름차순으로 정렬하고, 가중이 낮은 간선에서 하나씩 연결한다.

이 때, 대응하는 간선에 접속하려고 하는 정점이 현재의 정점과 사이클 구조를 이루지 않아야 한다.

static long kruskal() {
	long result = 0;
	int cnt = 0;
	for (Edge edge : edges) {
		// 두 간선이 싸이클이 형성되지 않았으면
		if (union(edge.from, edge.to)) {
			result += edge.weight; // 가중치 누적
			if (++cnt == V-1) break; // 모든 노드를 연결했으면 break;
		}
	}
	return result;
}

PRIM 알고리즘

각 정점으로 이어지는 간선 중에서 하나씩 선택해서 MST를 만드는 방식이다.

이 때, 우선 순위 큐를 이용하여, 선택된 정점에 인접하는 정점 중 가장 가까운 정점을 선택한다.

간선을 중심으로 탐색할지 혹은 정점을 중심으로 탐색할지에 따라 크루스컬과 프림을 적절히 선택하면 좋은 것 같다.

간선이 적으면 크루스컬, 그렇지 않으면 프림 알고리즘이 탐색에 유리하다.

static int prim() {
	pq.offer(new Edge(1, 0)); // 임의의 정점부터 시작
	int total = 0, cnt = 0;
	while (!
pq.isEmpty()) {
		Edge cur = pq.poll(); // 가중치가 낮은 간선을 가진 정점부터 선택
		int node = cur.to;
		int cost = cur.weight;
		if(v(node)) continue; // 이미 방문했던 노드라면 continue;
		v(node) = true; // 노드 방문 처리
		total += cost;
		for (Edge edge : edges(node)) // 현재 정점과 인접한 정점들의 간선 추가
			if (!
v(edge.to)) pq.offer(edge);
		if (++cnt == V) break;
	}
	return total;
}

풀코드(KRUSKAL)

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

public class Main {
	
	static class Edge implements Comparable<Edge> {
		int from, to, weight;
		public Edge(int from, int to, int weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}
		@Override
		public int compareTo(Edge o) {
			return Integer.compare(weight, o.weight);
		}
	}
	
	static int V, E;
	static int () p;
	static Edge () edges;
	
	static void make() {
		p = new int(V+1);
		for (int i = 1; i <= V; i++) p(i) = i;
	}
	
	static int find(int a) {
		if (p(a) == a) return a;
		return p(a) = find(p(a));
	}
	
	static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		if (aRoot == bRoot) return false;
		p(bRoot) = aRoot;
		return true;
	}
	
	static long kruskal() {
		long result = 0;
		int cnt = 0;
		for (Edge edge : edges) {
			// 두 간선이 싸이클이 형성되지 않았으면
			if (union(edge.from, edge.to)) {
				result += edge.weight;
				if (++cnt == V-1) break;
			}
		}
		return result;
	}
	
	public static void main(String() args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		edges = new Edge(E);
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			edges(i) = new Edge(from, to, weight); // 간선별로 연결된 정점과 가중치 등록
		}
		Arrays.sort(edges); // 가중치별로 정렬
		make(); // 각 노드 서로소 집합 생성
		// 크루스칼 알고리즘 최소 가중치 합 출력
		System.out.println(kruskal());
		br.close();
	}
}

풀 코드 (PRIM)

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

public class Main {
	
	static class Edge implements Comparable<Edge> {
		int to, weight;
		public Edge(int to, int weight) {
			this.to = to;
			this.weight = weight;
		}
		@Override
		public int compareTo(Edge o) {
			return Integer.compare(weight, o.weight);
		}
	}
	
	static int V, E;
	static boolean () v;
	static List<Edge>() edges;
	static PriorityQueue<Edge> pq = new PriorityQueue<>();
	
	static int prim() {
		pq.offer(new Edge(1, 0));
		int total = 0, cnt = 0;
		while (!
pq.isEmpty()) {
			Edge cur = pq.poll();
			int node = cur.to;
			int cost = cur.weight;
			if(v(node)) continue; // 이미 방문했던 노드라면 continue;
			v(node) = true; // 노드 방문 처리
			total += cost;
			for (Edge edge : edges(node))
				if (!
v(edge.to)) pq.offer(edge);
			if (++cnt == V) break;
		}
		return total;
	}
	
	public static void main(String() args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		edges = new ArrayList(V+1);
		for (int i = 1; i <= V; i++)edges(i) = new ArrayList<>();
		v = new boolean(V+1);
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			edges(from).add(new Edge(to, weight));// 무향 그래프이므로, 양방향에 추가!
!
!

			edges(to).add(new Edge(from, weight));
		}
		System.out.println(prim());
		br.close();
	}
}

회고

먼저 크루스컬로 제출하고 프림 알고리즘을 공부하기 위해 프림으로도 한 번 풀어 보았습니다.

간선 정보를 양방향으로 등록하지 않았고 여러 번 잘못됐다.

양방향 가중치 그래프에 사용되는 것을 잊지 마십시오.