5주차 알고리즘 - 최소신장트리 (MST)

- MST : Minimum Spanning Tree

- 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법 : 크루스칼, 프림

 

노드와 간선정보가 주어졌을 때 최소가 되게 노드들을 한 번만 연결하는 방법

 

MST 관련 문제들은 내부 알고리즘은 동일. 문제 파악한 후 MST 형태인 것만 떠올면 풀 수 있음

 

- 크루스칼 (Kruskal) 알고리즘 

  · 간선 중 최소 값을 가진 간선부터 연결

  · 사이클 발생 시 다른 간선 선택

  · 주로 간선 수가 적을 때 사용

  · O(Elog E)

- 간선 정보들을 오름차순 Sorting 작업 필요

- 사이클 발생 체크하는 Union-Find 테이블

초기 : 각 자기 자신으로 초기화

1. 처음에 가장 작은 가중치인 1을 선택해서 1 - 3 노드를 연결하면 3의 부모노드는 연결된, 자기자신보다 더 작은 숫자인 1로 업데이트 -> 부모노드가 같은 것 끼리 연결돼있음을 알려줌.

2. 그다음 작은 가중치인 2를 선택, 2 - 5 연결. 5의 부모노드를 2로 업데이트

3. 다음 가중치 5 선택. 5 - 6 연결 6의 부모노드는 5가 가진 부모노드값 2로 업데이트

4. 가중치 7 선택 2 - 6 연결하면 6의 부모노드는 이미 2였으므로 이미 연결된 애들임을 알 수 있음.-> 사이클 발생 연결X

5. 가중치 8. 6 -1 연결하면  6의 부모노드와 6과 같은 부모노드를 가지는 5, 2노드의 부모노드를 모두 1로 업데이트

6. 가중치 9. 1 -2 연결하면 이미 2의 부모노드가 1이므로 사이클 발생. 연결 X

7. 가중치 12. 3 - 4 연결후 4의 부모노드를 3의 부모노드인 1로 업데이트

8. 가중치 13. 2 - 4 연결하면 부모노드가 1로 같으므로 사이클 발생 연결X

9. 가중치 17. 4 - 7 연결하고 7의 부모노드 1로 업데이트

10. 가중치 20. 5 - 7 연결하면 둘의 부모노드가 1로 같으므로 사이클 발생. 연결 X

 

Union-Find의 모든 부모노드가 1로 변경되면서 연결이 되었음을 확인.

 

---

- 프림 (prim) 알고리즘

  · 임의의 노드에서 시작

  · 연결된 노드들의 간선 중 낮은 가중치를 갖는 간선 선택

  · 간선의 갯수가 많을 때 크루스칼 보다 유리

  · O(Elog V) -> Priority Queue를 이용했을 때

 

초기 : 방문 여부를 알려줄 visited 배열을 모두 0으로 초기화

간선 sorting할 필요 X 따라서 간선의 갯수가 많을 때 크루스칼 보다 유리

 

1. 임의의 노드 1번 선택 1의 visited 1로 업데이트

2. 1과 연결된 간선 중 가장 낮은 1을 선택. 3의 visited 1로 업데이트

3. 이제 연결된 간선 중에서는 8, 9, 12가 있음 그 중 가장 작은 8 선택. 6의 visited 1로 업데이트

4. 연결된 간선은 7,5,9,12가 있음. 그 중 가장 작은 5 선택. 5의 visited 1로 업데이트

5. 연결된 간선 : 2,12,20 중 가장 작은 2 선택. 2의 visited 1로 업데이트

6. 연결된 간선 : 7,9,12,13중 가장 작은 7 선택시 6이 이미 방문했으므로 그다음 9선택. 1도 방문했으므로 그다음 12선택. 4의 visited를 1로 업데이트.

7. 연결된 간선 : 13, 17 중 13은 2를 이미 방문했으므로 17선택. 7의 visited를 1로 바꿈.

 

---

<크루스칼 알고리즘 구현>

java

닫기 줄바꿈

// 알고리즘 - 최소 신장 트리
// 크루스칼 알고리즘

import java.util.Arrays;

public class Practice {

​​​​static int parents[]; //Union-Find를 위한 배열

​​​​public static int kruskal(int[][] data, int v, int e) {
​​​​​​​​int weightSum = 0;

​​​​​​​​Arrays.sort(data, (x, y) -> x[2] - y[2]); //간선을 기준으로 오름차순 sorting

​​​​​​​​parents = new int[v + 1];
​​​​​​​​for (int i = 1; i < v + 1; i++) {
​​​​​​​​​​​​parents[i] = i; //각각의 위치에 자기자신으로 초기화
​​​​​​​​}

​​​​​​​​for (int i = 0; i < e ; i++) {
​​​​​​​​​​​​if (find(data[i][0]) != find(data[i][1])) { //서로 연결이 되어있지 않은 케이스
​​​​​​​​​​​​​​​​union(data[i][0], data[i][1]);
​​​​​​​​​​​​​​​​weightSum += data[i][2];
​​​​​​​​​​​​}
​​​​​​​​​​​​System.out.println(Arrays.toString(parents));
​​​​​​​​}

​​​​​​​​return weightSum;
​​​​}

​​​​public static void union (int a, int b) { //연결이 되었을 때 두 개의 노드를 같은 집합으로 묶어줌.
​​​​​​​​int aP = find(a);
​​​​​​​​int bP = find(b);

​​​​​​​​if (aP != bP) {
​​​​​​​​​​​​parents[aP] = bP;
​​​​​​​​}
​​​​}
​​​​public static int find(int a) { //a라는 노드가 최종적으로 어디 연결되어있는지 찾아주는 메소드
​​​​​​​​if (a == parents[a]) {
​​​​​​​​​​​​return a;
​​​​​​​​}
​​​​​​​​return parents[a] = find(parents[a]); //사이클 체크를 위해 부모노드의 같은 부모로 계속해서 업데이트 해주는 부분
​​​​}
​​​​public static void main(String[] args) {
​​​​​​​​// Test code
​​​​​​​​int v = 7;
​​​​​​​​int e = 10;
​​​​​​​​int[][] graph = {{1, 3, 1}, {1, 2, 9}, {1, 6, 8}, {2, 4, 13}, {2, 5, 2}, {2, 6, 7}, {3, 4, 12}, {4, 7, 17}, {5, 6, 5}, {5, 7, 20}};

​​​​​​​​System.out.println(kruskal(graph, v, e));
​​​​}
}

근데 이렇게 하면 결과는 잘 나오지만 이론처럼 모든 Parents 값이 1로 맞춰지지 않는다. 

Union 메소드에서 parents[bP] = aP로 바꿔주니까 됐다.

사이클 체크만 하면 돼서 의미 없나 ?

 

---

<프림 알고리즘 구현>

우선순위 큐, visited 배열 사용

java

닫기 줄바꿈

// 프림 알고리즘


import java.sql.Array;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Practice {
​​​​static class Node {
​​​​​​​​int to;
​​​​​​​​int weight;

​​​​​​​​public Node(int to, int weight) {
​​​​​​​​​​​​this.to = to;
​​​​​​​​​​​​this.weight = weight;
​​​​​​​​}
​​​​}
​​​​public static int prim(int [][]data, int v, int e) {
​​​​​​​​int weightSum = 0;

​​​​​​​​ArrayList <ArrayList<Node>> graph = new ArrayList<>();

​​​​​​​​for (int i = 0; i < v + 1; i++) {
​​​​​​​​​​​​graph.add(new ArrayList<>());
​​​​​​​​}
​​​​​​​​for (int i = 0; i < e; i++) { //간선 정보 양방향 연결
​​​​​​​​​​​​graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
​​​​​​​​​​​​graph.get(data[i][1]).add(new Node(data[i][0], data[i][2]));
​​​​​​​​}

​​​​​​​​boolean[] visited = new boolean[v + 1];
​​​​​​​​PriorityQueue <Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);
​​​​​​​​pq.offer(new Node(1, 0));

​​​​​​​​int cnt = 0;
​​​​​​​​while (!pq.isEmpty()) {
​​​​​​​​​​​​Node cur = pq.poll();
​​​​​​​​​​​​cnt += 1;

​​​​​​​​​​​​if (visited[cur.to]) {
​​​​​​​​​​​​​​​​continue;
​​​​​​​​​​​​}
​​​​​​​​​​​​visited[cur.to] = true;
​​​​​​​​​​​​weightSum += cur.weight;

​​​​​​​​​​​​if (cnt == v) {
​​​​​​​​​​​​​​​​return weightSum;
​​​​​​​​​​​​}

​​​​​​​​​​​​for (int i = 0; i < graph.get(cur.to).size(); i++) {
​​​​​​​​​​​​​​​​Node adjNode = graph.get(cur.to).get(i);
​​​​​​​​​​​​​​​​if (visited[adjNode.to]) {
​​​​​​​​​​​​​​​​​​​​continue;
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​pq.offer(adjNode);
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​return weightSum;
​​​​}

​​​​public static void main(String[] args) {
​​​​​​​​// Test code
​​​​​​​​int v = 7;
​​​​​​​​int e = 10;
​​​​​​​​int[][] graph = {{1, 3, 1}, {1, 2, 9}, {1, 6, 8}, {2, 4, 13}, {2, 5, 2}, {2, 6, 7}, {3, 4, 12}, {4, 7, 17}, {5, 6, 5}, {5, 7, 20}};

​​​​​​​​System.out.println(prim(graph, v, e));
​​​​}
}

---

Practice 1)

// 2250년, 인류는 지구 뿐 아니라 여러 행성을 다니며 살고 있다.
// 이 행성 간을 빨리 오가기 위해 새롭게 터널을 구축하려 한다.

// 행성은 (x, y, z) 좌표로 주어진다.
// 행성1: (x1, y1, z1), 행성2: (x2, y2, z2)
// 이 때 행성간 터널 연결 비용은 min(|x1-x2|, |y1-y2|, |z1-z2|) 로 계산한다.

// n 개의 행성 사이를 n-1 개의 터널로 연결하는데 드는 최소 비용을 구하는 프로그램을 작성하세요.

// 입출력 예시
// 입력:
// data = {{11, -15, -15}, {14, -5, -15}, {-1, -1, -5}, {10, -4, -1}, {19, -4, 19}}
// 출력: 4

* n 개를 n -1 개로 연결한다는게 MST고 최소비용까지 나왔으니 명확해짐.

- Point클래스 : 행성 x, y, z값 관리

- Edge클래스 : 행성간의 간선 정보 관리

- 각각 x축, y축 z축 기준으로 정렬하고 순차적으로 요소값의 차이가 weight가 되어 edges 리스트에 모두 모음.

- 모은 edges 리스트를 기준으로 kruskal 메소드를 통해 행성과 행성을 연결하는데 최소 비용을 구함.

와 ! 갑자기 좀 깨달음을 얻었다.

x, y, z 축간 모든 행성들의 가중치를 edges배열에 저장, Edge는 weight기준 오름차순 정렬

kruskal에서 가중치 제일 작은 것 부터 연결시켜주는데 추후에 다른 축 값이 나온다고해도 앞에서 나온 더 작은 가중치 값에 의해 이미 행성들이 연결이 되어있으므로 또 연결하지 않음 !

java

닫기 줄바꿈

// Practice1
// 2250년, 인류는 지구 뿐 아니라 여러 행성을 다니며 살고 있다.
// 이 행성 간을 빨리 오가기 위해 새롭게 터널을 구축하려 한다.

// 행성은 (x, y, z) 좌표로 주어진다.
// 행성1: (x1, y1, z1), 행성2: (x2, y2, z2)
// 이 때 행성간 터널 연결 비용은 min(|x1-x2|, |y1-y2|, |z1-z2|) 로 계산한다.

// n 개의 행성 사이를 n-1 개의 터널로 연결하는데 드는 최소 비용을 구하는 프로그램을 작성하세요.

// 입출력 예시
// 입력:
// data = {{11, -15, -15}, {14, -5, -15}, {-1, -1, -5}, {10, -4, -1}, {19, -4, 19}}
// 출력: 4


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Practice {
​​​​static class Point {
​​​​​​​​int idx;
​​​​​​​​int x;
​​​​​​​​int y;
​​​​​​​​int z;

​​​​​​​​public Point(int idx, int x, int y, int z) {
​​​​​​​​​​​​this.idx = idx;
​​​​​​​​​​​​this.x = x;
​​​​​​​​​​​​this.y = y;
​​​​​​​​​​​​this.z = z;
​​​​​​​​}
​​​​}

​​​​static class Edge implements Comparable<Edge>{
​​​​​​​​int from;
​​​​​​​​int to;
​​​​​​​​int 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 this.weight - o.weight;
​​​​​​​​}
​​​​}
​​​​static int parents[]; //Union-find를 위한 배열
​​​​static ArrayList<Edge> edges;

​​​​public static int solution(int[][] data) {
​​​​​​​​int n = data.length; //행성 갯수

​​​​​​​​Point []points = new Point[n]; //n개의 행성 좌표 관리 배열
​​​​​​​​for (int i = 0; i < n; i++) {
​​​​​​​​​​​​points[i] = new Point(i, data[i][0], data[i][1], data[i][2]);
​​​​​​​​}
​​​​​​​​edges = new ArrayList<>();

​​​​​​​​//크루스칼 이용할 건데 각 축 값의 최솟값을 구해야하니까
​​​​​​​​//x축, y축, z축 기준 간선을 모두 모아서 크루스칼 적용 -> 이 문제의 응용점

​​​​​​​​//x축 기준 간선 추가
​​​​​​​​Arrays.sort(points, (p1, p2) -> p1.x - p2.x);
​​​​​​​​for (int i = 0; i < n - 1; i++) {
​​​​​​​​​​​​int weight = Math.abs(points[i].x - points[i + 1].x);

​​​​​​​​​​​​edges.add(new Edge(points[i].idx, points[i + 1].idx, weight));
​​​​​​​​}
​​​​​​​​//y축 기준 간선 추가
​​​​​​​​Arrays.sort(points, (p1, p2) -> p1.y - p2.y);
​​​​​​​​for (int i = 0; i < n - 1; i++) {
​​​​​​​​​​​​int weight = Math.abs(points[i].y - points[i + 1].y);
​​​​​​​​​​​​edges.add(new Edge(points[i].idx, points[i + 1].idx, weight));
​​​​​​​​}
​​​​​​​​//z축 기준 간선 추가
​​​​​​​​Arrays.sort(points, (p1, p2) -> p1.z - p2.z);
​​​​​​​​for (int i = 0; i < n - 1; i++) {
​​​​​​​​​​​​int weight = Math.abs(points[i].z - points[i + 1].z);
​​​​​​​​​​​​edges.add(new Edge(points[i].idx, points[i + 1].idx, weight));
​​​​​​​​}
​​​​​​​​for (Edge i : edges) {
​​​​​​​​​​​​System.out.println(i.from+" "+i.to+" "+i.weight);
​​​​​​​​}
​​​​​​​​Collections.sort(edges); //weight값 기준 오름차순 정렬
​​​​​​​​System.out.println("정렬 후");
​​​​​​​​for (Edge i : edges) {
​​​​​​​​​​​​System.out.println(i.from+" "+i.to+" "+i.weight);
​​​​​​​​}
​​​​​​​​//kruskal
​​​​​​​​return kruskal(n, edges);
​​​​}

​​​​public static int kruskal(int n, ArrayList <Edge>edges) {
​​​​​​​​parents = new int[n];

​​​​​​​​for (int i = 0; i < n; i++) {
​​​​​​​​​​​​parents[i] = i; //자기자신으로 초기화
​​​​​​​​}

​​​​​​​​int weightSum = 0;
​​​​​​​​for (int i = 0; i < edges.size(); i++) {
​​​​​​​​​​​​Edge edge = edges.get(i);

​​​​​​​​​​​​if (find(edge.to) != find(edge.from)) {
​​​​​​​​​​​​​​​​union(edge.to, edge.from);
​​​​​​​​​​​​​​​​weightSum += edge.weight;
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​return weightSum;
​​​​}

​​​​public static void union(int a, int b) {
​​​​​​​​int aP = find(a);
​​​​​​​​int bP = find(b);

​​​​​​​​if (aP != bP) {
​​​​​​​​​​​​parents[aP] = bP;
​​​​​​​​}
​​​​}
​​​​public static int find(int a) {
​​​​​​​​if (a == parents[a]) {
​​​​​​​​​​​​return a;
​​​​​​​​}
​​​​​​​​return parents[a] = find(parents[a]);
​​​​}

​​​​public static void main(String[] args) {
​​​​​​​​// Test code
​​​​​​​​int[][] data = {{11, -15, -15}, {14, -5, -15}, {-1, -1, -5}, {10, -4, -1}, {19, -4, 19}};
​​​​​​​​System.out.println(solution(data));
​​​​}
}

---

Practice 2)

// V 개의 건물과 E 개의 도로로 구성된 도시가 있다.
// 도로는 양방향이고 연결된 도로는 유지하는데 비용이 든다.

// 새롭게 도시 계획을 개편하며 기존의 도시를 두 개의 도시로 분할해서 관리하고자 한다.
// 도시에는 하나 이상의 건물이 있어야 하고,
// 도시 내의 임의의 두 건물은 도로를 통해 이동 가능해야 한다.
// 두 건물 간 도로가 직접 연결이 되지 않고 다른 건물을 통해서 이동해도 가능하다.
// 새롭게 개편하는 도시 계획에 따라 구성했을 때 최소한의 도로 유지비 비용 계산 프로그램을 작성하세요.

// 입출력 예시
// 입력:
// v: 7
// e: 12
// data: {{1, 2, 3}, {1, 3, 2}, {1, 6, 2}, {2, 5, 2},
// {3, 2, 1}, {3, 4, 4}, {4, 5, 3}, {5, 1, 5},
// {6, 4, 1}, {6, 5, 3}, {6, 7, 4}, {7, 3, 6}}
// 출력: 8

* 두 건물간 도로가 직접 연결이 되지 않고 다른 건물을 통해서 이동 가능 -> 여기까지만 읽어도 MST

도로들을 최소한의 비용으로 다 이은다음 가장 큰 비용을 끊어주면 됨.

 

java

닫기 줄바꿈

// Practice2
// V 개의 건물과 E 개의 도로로 구성된 도시가 있다.
// 도로는 양방향이고 연결된 도로는 유지하는데 비용이 든다.

// 새롭게 도시 계획을 개편하며 기존의 도시를 두 개의 도시로 분할해서 관리하고자 한다.
// 도시에는 하나 이상의 건물이 있어야 하고,
// 도시 내의 임의의 두 건물은 도로를 통해 이동 가능해야 한다.
// 두 건물 간 도로가 직접 연결이 되지 않고 다른 건물을 통해서 이동해도 가능하다.
// 새롭게 개편하는 도시 계획에 따라 구성했을 때 최소한의 도로 유지비 비용 계산 프로그램을 작성하세요.

// 입출력 예시
// 입력:
// v: 7
// e: 12
// data: {{1, 2, 3}, {1, 3, 2}, {1, 6, 2}, {2, 5, 2},
//        {3, 2, 1}, {3, 4, 4}, {4, 5, 3}, {5, 1, 5},
//        {6, 4, 1}, {6, 5, 3}, {6, 7, 4}, {7, 3, 6}}
// 출력: 8


import java.util.ArrayList;
import java.util.PriorityQueue;

public class Practice {
​​​​static class Node {
​​​​​​​​int to;
​​​​​​​​int weight;

​​​​​​​​public Node(int to,int weight) {
​​​​​​​​​​​​this.to = to;
​​​​​​​​​​​​this.weight = weight;
​​​​​​​​}
​​​​}
​​​​static ArrayList <ArrayList<Node>> graph;
​​​​static boolean []visited;
​​​​public static void solution(int v, int e, int[][] data) {
​​​​​​​​graph = new ArrayList<>();
​​​​​​​​for (int i = 0; i < v + 1; i++) {
​​​​​​​​​​​​graph.add(new ArrayList<>());
​​​​​​​​}
​​​​​​​​for (int i = 0; i < e; i++) {
​​​​​​​​​​​​graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
​​​​​​​​​​​​graph.get(data[i][1]).add(new Node(data[i][0], data[i][2]));
​​​​​​​​}
​​​​​​​​visited = new boolean[v + 1];

​​​​​​​​System.out.println(prim());
​​​​}
​​​​public static int prim() {
​​​​​​​​PriorityQueue <Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);

​​​​​​​​pq.offer(new Node(1, 0));
​​​​​​​​int weightSum = 0;
​​​​​​​​int max = Integer.MIN_VALUE;
​​​​​​​​while (!pq.isEmpty()) {
​​​​​​​​​​​​Node cur = pq.poll();

​​​​​​​​​​​​if (visited[cur.to]) {
​​​​​​​​​​​​​​​​continue;
​​​​​​​​​​​​}
​​​​​​​​​​​​visited[cur.to] = true;
​​​​​​​​​​​​weightSum += cur.weight;

​​​​​​​​​​​​max = Math.max(max, cur.weight);

​​​​​​​​​​​​for (int i = 0; i < graph.get(cur.to).size() ; i++) {
​​​​​​​​​​​​​​​​Node adjNode = graph.get(cur.to).get(i);

​​​​​​​​​​​​​​​​if (visited[adjNode.to] == true) {
​​​​​​​​​​​​​​​​​​​​continue;
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​pq.offer(adjNode);
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​return weightSum - max;
​​​​}
​​​​public static void main(String[] args) {
​​​​​​​​// Test code
​​​​​​​​int v = 7;
​​​​​​​​int e = 12;
​​​​​​​​int[][] data = {{1, 2, 3}, {1, 3, 2}, {1, 6, 2}, {2, 5, 2},
​​​​​​​​​​​​​​​​{3, 2, 1}, {3, 4, 4}, {4, 5, 3}, {5, 1, 5},
​​​​​​​​​​​​​​​​{6, 4, 1}, {6, 5, 3}, {6, 7, 4}, {7, 3, 6}};
​​​​​​​​solution(v, e, data);
​​​​}
}

어떻게 edge리스트를 구성할지가 관건같다.