[알고리즘] 최소 신장 트리 - 크루스칼(Kruskal)과 프림(Prim)

About this offer

최소 신장 트리(MST)를 구하는 대표적인 알고리즘인 크루스칼과 프림을 정리한다. 두 알고리즘 모두 그래프의 모든 정점을 연결하면서 간선 가중치의 합을 최소로 만드는 것 이 목적이다. 두 알고리즘의 가장 큰 차이는 MST를 만드는 방식이다. 알고리즘 기준 핵심 자료구조 크루스칼 간선 중심 Union-Find 프림 정점 중심 visited , minEdge 핵심은 다음과 같다. 크루스칼 : 전체 간선을 가중치 순으로 정렬하고, 사이클이 발생하지 않는 간선을 작은 것부터 선택한다. 프림 : 하나의 정점에서 시작해 현재 트리와 연결할 수 있는 정점 중 가장 적은 비용으로 연결되는 정점을 선택한다. 1. 최소 신장 트리(MST) 신장 트리(Spanning Tree)는 그래프의 모든 정점을 연결하면서 사이클이 없는 트리 를 의미한다. 정점이 V 개라면 신장 트리가 가지는 간선의 개수는 항상 V-1 개이다. 이 중에서 사용한 간선들의 가중치 합이 가장 작은 신장 트리를 최소 신장 트리(Minimum Spanning Tree, MST) 라고 한다. 예를 들어 여러 도시를 도로로 연결해야 할 때, 모든 도시를 연결하면서 도로 건설 비용을 최소화하는 문제에서 사용할 수 있다. 2. 크루스칼(Kruskal) 크루스칼은 간선을 기준으로 MST를 만드는 알고리즘 이다. 전체 간선을 가중치 기준으로 오름차순 정렬한 뒤, 가장 가중치가 작은 간선부터 하나씩 확인한다. 이때 간선을 연결했을 때 사이클이 발생하지 않는 경우에만 MST에 포함한다. 동작 과정은 다음과 같다. 모든 간선을 가중치 기준 오름차순으로 정렬한다. 가장 가중치가 작은 간선부터 확인한다. 두 정점이 이미 같은 집합인지 확인한다. 다른 집합이면 두 정점을 연결한다. 같은 집합이면 사이클이 발생하므로 선택하지 않는다. 간선을 V-1 개 선택하면 종료한다. 사이클 발생 여부를 빠르게 판단하기 위해 Union-Find 를 사용한다. 3. Union-Find Union-Find는 여러 정점이 같은 집합에 포함되어 있는지 확인하고, 서로 다른 두 집합을 하나로 합치는 자료구조이다. 크게 find 와 union 두 연산을 사용한다. makeSets 처음에는 모든 정점이 서로 연결되어 있지 않기 때문에 각 정점의 부모를 자기 자신으로 설정한다. static void makeSets() { for (int i = 0; i < V; i++) { parents[i] = i; } } 예를 들어 정점이 4개라면 처음에는 다음과 같다. 정점 0 1 2 3 parents 0 1 2 3 각 정점이 하나의 독립적인 집합인 상태이다. find find 는 해당 정점이 속한 집합의 대표 정점(루트)을 찾는다. static int find(int a) { if (parents[a] == a) { return a; } return parents[a] = find(parents[a]); } 부모를 계속 따라가면서 최종 루트를 찾는다. 3 → 2 → 1 과 같은 구조라면 find(3) 의 결과는 1 이다. return parents[a] = find(parents[a]); 에서는 최종 루트를 찾은 뒤 parents[a] 에 바로 저장한다. 따라서 3 → 2 → 1 이었던 구조가 이후에는 3 → 1 2 → 1 처럼 변경된다. 이를 경로 압축(Path Compression) 이라고 한다. union union 은 두 정점이 서로 다른 집합에 있다면 하나의 집합으로 합친다. static boolean union(int a, int b) { int rootA = find(a); int rootB = find(b); if (rootA == rootB) { return false; } parents[rootB] = rootA; return true; } 먼저 두 정점의 대표 정점을 찾는다. int rootA = find(a); int rootB = find(b); 두 대표가 같다면 이미 연결되어 있다는 의미이다. if (rootA == rootB) { return false; } 이 상태에서 다시 간선을 연결하면 사이클이 발생하기 때문에 해당 간선을 선택하지 않는다. 반대로 대표가 다르다면 parents[rootB] = rootA; 로 두 집합을 하나로 합친다. 즉 크루스칼에서는 다음 조건이 핵심이다. find(a) == find(b) → 이미 같은 집합 → 연결하면 사이클 발생 → 선택 X find(a) != find(b) → 서로 다른 집합 → 연결해도 사이클 발생 X → 선택 O 4. 크루스칼 코드 간선 하나를 다음과 같이 배열로 저장한다. edge[0] = 시작 정점 edge[1] = 도착 정점 edge[2] = 가중치 전체 코드는 다음과 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class MST_Kruskal { // 간선 정보를 2차원 배열로 저장 // edgeList[i][0] = 시작 정점 // edgeList[i][1] = 도착 정점 // edgeList[i][2] = 가중치 static int[][] edgeList; static int[] parents; static int V, E; // Union-Find 초기화 // 각 정점의 부모를 자기 자신으로 설정 static void makeSets() { for (int i = 0; i < V; i++) { parents[i] = i; } } // 해당 정점이 속한 집합의 대표 정점 찾기 static int find(int a) { // 자기 자신이 부모라면 루트 if (parents[a] == a) { return a; } // 최종 루트를 찾아 저장 return parents[a] = find(parents[a]); } // 두 정점이 속한 집합 합치기 static boolean union(int a, int b) { int rootA = find(a); int rootB = find(b); // 이미 같은 집합이라면 사이클 발생 if (rootA == rootB) { return false; } // 서로 다른 집합이면 합치기 parents[rootB] = rootA; return true; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); V = Integer.parseInt(st.nextToken()); E = Integer.parseInt(st.nextToken()); edgeList = new int[E][3]; parents = new int[V]; // 간선 입력 for (int i = 0; i < E; i++) { st = new StringTokenizer(br.readLine()); edgeList[i][0] = Integer.parseInt(st.nextToken()); edgeList[i][1] = Integer.parseInt(st.nextToken()); edgeList[i][2] = Integer.parseInt(st.nextToken()); } // 가중치 기준 오름차순 정렬 Arrays.sort( edgeList, (a, b) -> Integer.compare(a[2], b[2]) ); // Union-Find 초기화 makeSets(); int result = 0; int cnt = 0; // 가중치가 작은 간선부터 확인 for (int[] edge : edgeList) { int from = edge[0]; int to = edge[1]; int weight = edge[2]; // 서로 다른 집합이라면 연결 if (union(from, to)) { result += weight; // MST는 V-1개의 간선을 사용 if (++cnt == V - 1) { break; } } } System.out.println(result); } } 크루스칼의 핵심 부분은 다음 코드이다. Arrays.sort( edgeList, (a, b) -> Integer.compare(a[2], b[2]) ); for (int[] edge : edgeList) { if (union(edge[0], edge[1])) { result += edge[2]; if (++cnt == V - 1) { break; } } } 먼저 모든 간선을 가중치 기준으로 정렬한다. 이후 가장 작은 간선부터 확인하면서 union() 이 성공한 경우에만 비용을 추가한다. union() 이 false 를 반환했다는 것은 두 정점이 이미 같은 집합이라는 의미이므로 해당 간선을 추가하면 사이클이 발생한다. 정점이 V 개인 MST는 간선을 V-1 개 사용하기 때문에 cnt == V-1 이 되면 탐색을 종료한다. 5. 프림(Prim) 프림은 정점을 기준으로 MST를 확장하는 알고리즘 이다. 크루스칼이 그래프 전체에서 가장 가중치가 작은 간선을 선택한다면, 프림은 하나의 정점에서 시작해서 현재 만들어진 트리와 연결할 수 있는 정점 중 가장 적은 비용으로 연결되는 정점 을 선택한다. 동작 과정은 다음과 같다. 시작 정점을 하나 선택한다. 아직 MST에 포함되지 않은 정점 중 가장 적은 비용으로 연결할 수 있는 정점을 찾는다. 해당 정점을 MST에 포함한다. 새롭게 선택된 정점과 연결된 간선을 확인한다. 기존보다 더 적은 비용으로 연결할 수 있다면 최소 비용을 갱신한다. 모든 정점이 선택될 때까지 반복한다. 프림에서는 주로 다음 두 배열을 사용한다. boolean[] visited; int[] minEdge; visited[i] 는 i 번 정점이 이미 MST에 포함되었는지를 나타낸다. minEdge[i] 는 현재 만들어진 MST에서 i번 정점을 연결하기 위해 필요한 최소 비용 을 저장한다. 6. minEdge 처음에는 어떤 정점도 연결하지 않았기 때문에 모든 값을 무한대로 설정한다. Arrays.fill(minEdge, Integer.MAX_VALUE); 0번 정점에서 시작한다면 minEdge[0] = 0; 으로 설정한다. 처음 상태는 다음과 같다. 정점 0 1 2 3 minEdge 0 INF INF INF 이후 새로운 정점이 MST에 포함될 때마다 인접 정점으로 더 저렴하게 이동할 수 있는지 확인한다. 예를 들어 현재 minEdge[2] = 5 인데 새롭게 선택된 정점에서 2번 정점으로 가는 비용이 3 이라면 5 > 3 이므로 minEdge[2] = 3; 으로 갱신한다. 7. 프림 코드 인접 리스트는 연결 리스트 형태로 구현한다. Node 에는 도착 정점, 가중치, 다음 간선의 주소를 저장한다. static class Node { int to, weight; Node next; public Node(int to, int weight, Node next) { this.to = to; this.weight = weight; this.next = next; } } 전체 코드는 다음과 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class MST_Prim { static int V, E; static Node[] adjList; static boolean[] visited; static int[] minEdge; // 간선 정보 저장 static class Node { int to, weight; Node next; public Node(int to, int weight, Node next) { this.to = to; this.weight = weight; this.next = next; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); V = Integer.parseInt(st.nextToken()); E = Integer.parseInt(st.nextToken()); adjList = new Node[V]; visited = new boolean[V]; minEdge = new int[V]; // 간선 입력 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()); // 무방향 그래프이므로 양방향 저장 adjList[from] = new Node(to, weight, adjList[from]); adjList[to] = new Node(from, weight, adjList[to]); } // 모든 정점의 최소 연결 비용을 무한대로 초기화 Arrays.fill(minEdge, Integer.MAX_VALUE); int result = 0; // 0번 정점부터 시작 minEdge[0] = 0; int c; for (c = 0; c < V; c++) { // STEP 1 // 아직 MST에 포함되지 않은 정점 중 // 가장 적은 비용으로 연결할 수 있는 정점 찾기 int min = Integer.MAX_VALUE; int minVertex = -1; for (int i = 0; i < V; i++) { if (!visited[i] && minEdge[i] < min) { min = minEdge[i]; minVertex = i; } } // 더 이상 연결할 수 있는 정점이 없다면 종료 if (minVertex == -1) { break; } // 선택한 정점을 MST에 포함 visited[minVertex] = true; // 해당 정점을 연결하기 위한 비용 추가 result += min; // STEP 2 // 선택된 정점과 연결된 정점들을 확인하여 // minEdge 갱신 for (Node temp = adjList[minVertex]; temp != null; temp = temp.next) { // 아직 MST에 포함되지 않았고 // 기존 비용보다 현재 간선이 더 저렴하다면 갱신 if (!visited[temp.to] && minEdge[temp.to] > temp.weight) { minEdge[temp.to] = temp.weight; } } } // 모든 정점을 연결했다면 MST 비용 출력 // 연결하지 못했다면 -1 System.out.println(c == V ? result : -1); } } 프림에서 핵심은 크게 두 단계이다. STEP 1. 가장 적은 비용으로 연결되는 정점 선택 for (int i = 0; i < V; i++) { if (!visited[i] && minEdge[i] < min) { min = minEdge[i]; minVertex = i; } } 아직 MST에 포함되지 않은 정점 중 minEdge 값이 가장 작은 정점을 선택한다. 즉 현재 MST에 가장 적은 비용으로 연결할 수 있는 정점을 찾는 과정이다. STEP 2. minEdge 갱신 for (Node temp = adjList[minVertex]; temp != null; temp = temp.next) { if (!visited[temp.to] && minEdge[temp.to] > temp.weight) { minEdge[temp.to] = temp.weight; } } 새로운 정점이 MST에 포함되면 새로운 간선을 사용할 수 있게 된다. 따라서 해당 정점과 연결된 정점들을 확인하면서 기존 minEdge 보다 더 저렴한 간선이 발견되면 값을 갱신한다. 이 두 과정을 모든 정점이 MST에 포함될 때까지 반복한다. 정리: 크루스칼과 프림의 차이 두 알고리즘 모두 MST를 만들지만 접근 방식에 차이가 있다. 구분 크루스칼 프림 기준 간선 중심 정점 중심 시작 정점 필요 없음 필요 선택 방법 전체 간선 중 가장 작은 간선 현재 트리에서 가장 싸게 연결되는 정점 사이클 방지 Union-Find visited 주요 자료구조 간선 배열, parents 인접 리스트, visited , minEdge 핵심 동작 정렬 → Union 정점 선택 → minEdge 갱신 종료 간선 V-1 개 선택 정점 V 개 선택 크루스칼은 그래프 전체의 간선을 기준으로 동작한다. 전체 간선 정렬 ↓ 가장 작은 간선 선택 ↓ Union-Find로 사이클 확인 ↓ V-1개 선택 프림은 하나의 정점에서 시작해 하나의 트리를 점점 확장한다. 시작 정점 선택 ↓ 가장 싸게 연결되는 정점 선택 ↓ visited 처리 ↓ 인접 정점의 minEdge 갱신 ↓ 모든 정점을 선택할 때까지 반복 결국 가장 큰 차이는 크루스칼은 간선을 하나씩 선택하면서 여러 집합을 합쳐 나가고, 프림은 하나의 정점에서 시작해 하나의 트리를 계속 확장한다는 것 이다. 시간 복잡도 크루스칼 크루스칼에서는 전체 간선을 정렬하는 과정이 가장 큰 비중을 차지한다. 간선이 E 개라면 정렬에 O(E log E) 가 필요하다. Union-Find의 find , union 연산은 경로 압축을 사용하면 매우 빠르게 동작하기 때문에 전체 시간 복잡도는 일반적으로 O(E log E) 로 본다. 프림 위 코드에서는 매번 방문하지 않은 정점 중 최소 minEdge 를 찾기 위해 모든 정점을 확인한다. for (int i = 0; i < V; i++) 이 작업을 V 번 반복하기 때문에 최소 정점 탐색에 O(V2) 가 필요하다. 인접 리스트의 간선을 확인하는 작업까지 포함하면 위 구현의 전체 시간 복잡도는 O(V2 + E) 이며 일반적으로 O(V2) 로 볼 수 있다. 우선순위 큐를 사용하는 방식으로 구현하면 프림의 시간 복잡도를 O(E log V) 수준으로 개선할 수 있다. 한 줄 정리 크루스칼 : 간선을 가중치 순으로 정렬하고 Union-Find를 이용해 사이클을 피하면서 V-1 개의 간선을 선택한다. 프림 : 하나의 정점에서 시작해 현재 트리에 가장 적은 비용으로 연결되는 정점을 선택하고 minEdge 를 갱신하는 과정을 반복한다.