BOJ#1197 최소 스패닝 트리

BOJ#1197 최소 스패닝 트리

* 문제

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

* 풀이

- MST(최소 스패닝 트리), 프림, 크루스칼 알고리즘, Union-Find 자료구조 설명

http://stack07142.tistory.com/54

- MST (Minimum Spanning Tree)를 구하는 방법으로 아래 2가지 알고리즘이 있습니다.

1) Prim's Algorithm, 프림

2) Kruskal Algorithm, 크루스칼

1197번 문제를 위 2가지 알고리즘으로 풀어보았습니다.

---

1. Prim's Algorithm, 프림

메모리 : 18848 KB, 시간 : 1244 MS

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; /* * BOJ#1197 최소 스패닝 트리 * https://www.acmicpc.net/problem/1197 */ public class Main_Prim { static final int INF = 100000000; public static void main(String[] args) throws IOException { int V; // V 그룹 정점의 개수 int E; // 간선의 개수 int[][] w; // 간선의 정보 int sumOfWeight = 0; // MST 가중치의 합 boolean[] visited; int numOfMST = 0; // MST 그룹 정점의 개수 int[] d; // MST 그룹에서 V그룹의 vertex까지의 거리 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(br.readLine()); V = Integer.parseInt(st.nextToken()); E = Integer.parseInt(st.nextToken()); visited = new boolean[V + 1]; w = new int[V + 1][V + 1]; d = new int[V + 1]; for (int i = 0; i < V + 1; i++) { d[i] = INF; visited[i] = false; for (int j = 0; j < V + 1; j++) { w[i][j] = INF; } } // 간선 정보 입력 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()); if (w[A][B] > C) { // 무방향 그래프 w[A][B] = C; w[B][A] = C; } } // Prim 알고리즘 // 초기값 numOfMST = 0; // MST[0] = 1; d[1] = 0; while (numOfMST < V) { int min = INF; int u = -1; // v 그룹에서 제일 가까운 node를 뽑는다. for (int i = 1; i < V + 1; i++) { if (!visited[i] && d[i] < min) { min = d[i]; u = i; } } // d 거리 갱신 for (int i = 1; i < V + 1; i++) { if (!visited[i] && w[u][i] != INF) { if (w[u][i] < d[i]) { d[i] = w[u][i]; } } } numOfMST++; sumOfWeight += min; visited[u] = true; } // 결과 출력 bw.write(String.valueOf(sumOfWeight)); bw.flush(); bw.close(); br.close(); } }

* 코드 해설

- 다익스트라 알고리즘과 비슷합니다.

- 그래프를 2개의 그룹으로 나눕니다. 하나는 MST 그룹, 하나는 V그룹

- 최초에는 당연히 V그룹만 있고, MST 그룹은 없겠죠?

- 프림 알고리즘에서는 시작점을 정해야 합니다. 시작점을 정하는 순간 MST 그룹은 정점이 1개 추가되는 것입니다.

- MST 그룹에서 인접한 V그룹의 정점까지의 거리(d 배열)를 갱신해줍니다. 그리고 d배열값이 가장 작은, 가장 가까운 V그룹의 정점을 MST 그룹의 다음 정점으로 선택하는 것입니다.

---

2. Kruskal Algorithm, 크루스칼

메모리 : 14148 KB, 시간 : 484 MS

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.PriorityQueue; import java.util.Queue; import java.util.StringTokenizer; /* * BOJ#1197 최소 스패닝 트리 * https://www.acmicpc.net/problem/1197 */ public class Main { static final int INF = 100000000; public static void main(String[] args) throws IOException { int V; // V 그룹 정점의 개수 int E; // 간선의 개수 int weightSumOfMST = 0; // MST 가중치의 합 int edgeNumOfMST = 0; // MST 정점의 개수 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(br.readLine()); V = Integer.parseInt(st.nextToken()); E = Integer.parseInt(st.nextToken()); // 간선 정보 입력 // Kruskal 알고리즘 Queue<Edge> edgePriorityQueue = new PriorityQueue<Edge>(); 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()); // 우선순위큐-간선의 Weight 기준으로 정렬 edgePriorityQueue.add(new Edge(A, B, C)); } UnionFind unionFind = new UnionFind(V); while (edgeNumOfMST < V && !edgePriorityQueue.isEmpty()) { Edge edge = edgePriorityQueue.poll(); // Union-Find로 사이클을 이루는지 확인 // 사이클을 이룬다면 if (unionFind.find(edge.v1) == unionFind.find(edge.v2)) { continue; } // 사이클을 이루지 않는다면 else { unionFind.union(edge.v1, edge.v2); weightSumOfMST += edge.weight; edgeNumOfMST++; } } // 결과 출력 bw.write(String.valueOf(weightSumOfMST)); bw.flush(); bw.close(); br.close(); } } class UnionFind { int[] root; public UnionFind(int V) { root = new int[V + 1]; initialize(); } public int find(int a) { if (root[a] < 0) { return a; } return root[a] = find(root[a]); } public void union(int a, int b) { int root1 = find(a); int root2 = find(b); // 이미 같은 그룹이라면 if (root1 == root2) { return; } // 다른 그룹이라면 // root1의 그룹이 더 작다면 (root1 < root2) if (root[root1] > root[root2]) { root1 ^= root2; root2 ^= root1; root1 ^= root2; } // root1과 root2를 결합하고, root2의 부모를 roo1로 설정 root[root1] += root[root2]; root[root2] = root1; } private void initialize() { for (int i = 0; i < root.length; i++) { root[i] = -1; } } // a를 포함하는 그룹의 정점의 개수를 확인하는 함수 public int size(int a) { return -root[find(a)]; } } class Edge implements Comparable<Edge> { int v1; int v2; int weight; Edge(int v1, int v2, int weight) { this.v1 = v1; this.v2 = v2; this.weight = weight; } @Override public int compareTo(Edge o) { return (this.weight > o.weight ? 1 : (this.weight == o.weight ? 0 : -1)); } }

* 코드 해설

- 간선의 weight를 기준으로 간선들을 정렬해야 하므로 우선순위 큐에 Edge 객체들을 넣어 주었습니다.

- Edge 객체들을 비교하려면 Comparable을 implements 해야 합니다.

  (어떻게 비교해야 하는지 모르기 때문에 compareTo 함수를 오버라이드 해서 구현해줍니다.)

- while loop의 (edgeNumOfMST < V) 조건

 : 최소 스패닝 트리의 조건은 (정점의 수 - 1 = 간선의 수) 입니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%231197_MST