알고리즘 최소비용신장트리(JAVA)

1060 : 최소비용신장트리

제한시간: 1Sec    메모리제한: 32mb
해결횟수: 860회    시도횟수: 2796회   

정보올림피아드 공부를 더욱 효율적으로 할 수 있도록 전국에 흩어져 있는 정올 학원들을 네트워크로 연결하려고 한다.그러나 모든 학원들을 네트워크로 연결하려면 너무 많은 비용이 필요하기 때문에 정올에서는 학원들을 연결하는 비용을 최소가 되게 하려고 한다. 학원들은연결되어 있는 다른 학원의 회선을 공유할 수 있다.

아래 그림과 같이 학원 사이를 연결하기 위한 비용이 주어지면 모든 학원을 연결하기 위한 최소의 비용을 구하는 프로그램을 작성하라.

 

 

 

첫줄에 학원의 수 N(3≤N≤100)이 주어진다.둘째 줄부터 NxN의 행렬로 100,000이하의 정수가 공백으로 구분되어 입력된다. 행렬의 i j는 i번 학원에서 j번 학원을 연결하기 위한 비용을 나타낸다.

학원들을 모두 연결하기 위한 최소 비용을 출력한다.

[Copy] 5 0 5 10 8 7 5 0 5 3 6 10 5 0 1 3 8 3 1 0 1 7 6 3 1 0

[Copy] 1

?

1. import java.util.Scanner;
2.  
3. public class Main
4. {
5.     private static Scanner sc;
6.     public static void main(String[] args) {
7.         sc = new Scanner(System.in);
8.  
9.         int N = sc.nextInt();
10.         int [][] map = new int[N][N];
11.         int len = 0;
12.         int [] label = new int[N];
13.         Vertex [] points = new Vertex[5050];
14.  
15.         for(int i = 0 ; i < N; ++i){
16.             label[i] = i;
17.             for(int j = 0; j < N; ++j){
18.                 map[i][j] = sc.nextInt();
19.                 if(i < j){
20.                     points[len++] = new Vertex(i, j, map[i][j]);
21.                 }
22.             }
23.         }      
24.         // 1. 정렬
25.         quickSort(points, 0, len-1);
26.  
27.         // 2. 어사이클
28.         int nodes = 0, index = 0;
29.         int cost = 0, tmp = 0;
30.         while(nodes < N-1)
31.         {
32.             if(label[points[index].x] != label[points[index].y])
33.             {
34.                 tmp = label[points[index].y];
35.                 for(int i = 0 ; i < N; ++i){
36.                     if(tmp == label[i])
37.                         label[i] = label[points[index].x];
38.                 }
39.                 cost += points[index].cost;
40.                 nodes++;
41.             }
42.             index++;
43.         }
44.  
45.         System.out.println(cost);
46.     }
47.  
48.  
49.     public static void quickSort(Vertex[] array, int s, int e) {
50.         if(s >= e){
51.             return;
52.         }
53.         int i = s + 1;
54.         int j = e;
55.         Vertex pivot = array[s];
56.  
57.         while (i <= j) {
58.             while (i <= e && array[i].cost <= pivot.cost)
59.                 i++;
60.             while (s + 1 <= j && pivot.cost <= array[j].cost)
61.                 j--;
62.  
63.             if (i <= j) {
64.                 Vertex temp = array[i];
65.                 array[i] = array[j];
66.                 array[j] = temp;
67.             } else {
68.                 array[s] = array[j];
69.                 array[j] = pivot;
70.             }
71.         }
72.         quickSort(array, s, j - 1 );
73.         quickSort(array, j + 1, e );
74.     }
75. }
76.  
77. class Vertex
78. {
79.     public int x;
80.     public int y;
81.     public int cost;
82.  
83.     Vertex(int x, int y, int cost)
84.     {
85.         this.x = x;
86.         this.y = y;
87.         this.cost = cost;
88.     }
89. }

그리디 알고리즘으로 풀 수 있는 대표적인 문제. 

특히 최소비용신장트리는 유명한 문제로 이를 해결하기 위한 알고리즘은 유명한 두 알고리즘이 있다. 

1. 크루스칼(Kruskal) 알고리즘

2. 프림(Prim) 알고리즘 

두 알고리즘은 보통 방향성을 가지지 않는 그래프에서 최소비용 혹은 최대효율을 만드는 신장트리(spanning tree - 모든 vertex를 포함하는 부분 집합)

에서 사용되고 다익스트라(Dijkstra) 알고리즘은 방향성을 가지는 그래프에서 특정 vertex에서 다른 vertex로 가는 최단경로를 푸는 문제에 주로 사용된다. 

크루스칼 알고리즘은 쉽게 설명하면 다음과 같다. 

1. 모든 edge를 가중치 별로 정렬한다. 

방향성을 가지지 않기 때문에 입력받은 map에서 중복되지 않는 edge만을 points 배열에 저장하였다. 

정렬은 Java내의 정렬을 사용해도 되나 quick sort를 구현해보았다. 

2. 가장 작은 가중치를 가진 edge을 선택한다. 

3. 선택한 edge가 cycle을 만들면 그 edge는 버린다. 

이때 구현을 위해 각각의 점에 label을 붙였고, 연결된 vertex끼리는 같은 label을 가져가도록 하였다. 

모든 vertex가 동일한 label을 가지고 있다면 모든 vertex는 연결된 것이다. 

4. 2, 3번을 반복하며 N개의 vertex가 있을 때 N-1개의 edge가 선택되면 알고리즘이 종료된다. (N개의 vertex는 N-1개의 edge로 연결이 가능하다.)