[백준 / Java] 1197번 : 최소 스패닝 트리

문제

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

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

예제 입력 1 복사

3 3
1 2 1
2 3 2
1 3 3

예제 출력 1 복사

3

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

1197번: 최소 스패닝 트리

---

문제 풀이

 해당 문제는 최소 신장 트리(MST)를 구하는 문제로 최소 신장 트리를 구하는 방법은 대표적으로 두가지 방법이 있다.

1. Prim 알고리즘       ->  2023.08.09 - [algorithm/theory] - Prim 알고리즘
2. Kruskal 알고리즘  ->  2023.08.10 - [algorithm/theory] - Kruskal 알고리즘

 해당 알고리즘 설명은 이전에 포스팅한 글을 참고하면 될 것 같다. 

 

최소 신장 트리 관련 문제는 처음 풀기 때문에 두 가지 방법 모두 사용하여 풀어보자.

 

1. Prim 알고리즘

프림 알고리즘 동작과정은 간단하다.

1. 임의의 간선을 선택한다.
2. 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택한다.
3. 모든 정점에 대하여 2번의 과정을 반복한다.

이를 적용하여 풀면 쉽게 답이 나온다.

import java.util.*;
import java.io.*;
public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static StringTokenizer st;

	public static int V;
	public static int E;
	public static Map<Integer,ArrayList<Node>> nodes = new HashMap<>();
	public static PriorityQueue<Node> pq = new PriorityQueue<>();
	
	public static class Node implements Comparable<Node>{

		int to;
		int val;
		
		public Node() {}

		public Node(int to,int val) {
			this.to = to;
			this.val = val;
		}
		@Override
		public int compareTo(Node o) {
			return (this.val - o.val);
		}

	}
	
	public static void main(String[] args) throws IOException{
		st = new StringTokenizer(br.readLine());
		
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		while(E --> 0) {
			st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			int val = Integer.parseInt(st.nextToken());
			
			
			
			if(!nodes.containsKey(n1)) 
				nodes.put(n1, new ArrayList<>());
			nodes.get(n1).add(new Node(n2,val));
			
			if(!nodes.containsKey(n2)) 
				nodes.put(n2, new ArrayList<>());
			nodes.get(n2).add(new Node(n1,val));
			

		}
		
		boolean[] visited = new boolean[V+1];
		int answer = 0;
		
		pq.add(new Node(1,0));
		
		while(!pq.isEmpty()) {
			Node cur = pq.poll();
			
			if(visited[cur.to]) continue;
			visited[cur.to] = true;
			answer+=cur.val;
			
			for(Node n : nodes.get(cur.to)) {
				if(!visited[n.to])
					pq.add(n);
			}
		}
		System.out.println(answer);
	}
}

 

 2. Kruskal 알고리즘

크루스칼 알고리즘 동작은 아래와 같다.

1. 간선을 오름차순으로 선택한다.
2. 이 때 해당 간선을 추가하였을 때 노드가 순환한다면 해당 간선을 추가하지 않는다.

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


////Kruskal 알고리즘
public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static StringTokenizer st;
	public static int INF = 100_000_000;
	public static int[] dx = {0,1,0,-1};
	public static int[] dy = {-1,0,1,0};

	public static int V;
	public static int E;
	public static int[] parent;
	public static Map<Integer,ArrayList<Node>> nodes = new HashMap<>();
	public static PriorityQueue<Node> pq = new PriorityQueue<>();
	
	public static class Node implements Comparable<Node>{
		int from;
		int to;
		int val;
		
		public Node() {}

		public Node(int from,int to,int val) {
			this.from = from;
			this.to = to;
			this.val = val;
		}
		@Override
		public int compareTo(Node o) {
			return (this.val - o.val);
		}

	}
	
	public static void main(String[] args) throws IOException{
		st = new StringTokenizer(br.readLine());
		
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		parent = new int[V+1];
		for(int i=1; i <= V; i++) {
			parent[i] = i;
		}
		
		while(E --> 0) {
			st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			int val = Integer.parseInt(st.nextToken());
			
			pq.add(new Node(n1,n2,val));
		}
		
		boolean[] visited = new boolean[V+1];
		int answer = 0;
		
		while(!pq.isEmpty()) {
			Node cur = pq.poll();
			
			
			int to = find(cur.to);
			int from = find(cur.from);
			
			if(!isSameParent(to,from)) {
				answer += cur.val;
				union(cur.to, cur.from);
			}
			
		}
		System.out.println(answer);
	}
	
	public static int find(int x) {
		if(parent[x] ==x ) return x;
		return parent[x] = find(parent[x]);
	}
	
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		if(x!= y) {
			parent[y] =x;
		}
	}
	
	public static boolean isSameParent(int x, int y ) {
		x = find(x);
		y = find(y);
		if(x==y) return true;
		else return false;
	}
}