[Swift] 크루스칼 알고리즘 ( MST 최소 신장 트리 )

1. MST(Minimum Spanning Tree)란?

MST(Minimum Spanning Tree, 최소 신장 트리)는 그래프의 모든 정점을 포함하면서

1. 정점 간 연결된 간선들의 가중치 합이 최소
2. 사이클을 포함하지 않는 트리

MST가 필요한 상황

1. 도시 간 도로 네트워크 구축
   • 최소 비용으로 모든 도시 연결
2. 통신 네트워크 설계
   • 모든 기기를 최소 비용으로 연결
3. 파이프라인 설계
   • 최소 비용으로 모든 지점 연결
4. 전기 배선망 구축
   • 모든 가구를 최소 비용으로 연결

 

2. 크루스칼 알고리즘

크루스칼 알고리즘은 MST를 찾는 대표적인 알고리즘

 

동작 원리

1. 모든 간선을 가중치 순으로 정렬
2. 가장 작은 가중치의 간선부터 선택
3. 선택한 간선이 사이클을 만들지 않으면 MST에 포함
4. 사이클 여부는 Union-Find 알고리즘으로 판단

Union-Find 알고리즘

• 서로소 집합, 상호 배타적 집합 (Disjoint-Set)이라고도 합니다.
• Find 연산과 Union 연산으로 구성됩니다.
• Find
  • 노드 A가 어떤 집합에 포함되어 있는지 찾는 연산입니다.
  • 부모 노드를 리턴합니다.
• Union
  • 노드 A가 속한 집합과 노드 B가 속한 집합을 합치는 연산입니다.

그래프 예시

위와 같은 그래프에서 Find 연산을 실행하면 다음과 같은 과정이 이어집니다.

1. parent 배열을 생성하여 각 노드들의 부모를 기록하도록 합니다. (초기값으로 자기 자신을 부모로 설정합니다.)

index	0	1	2	3	4	5
parent 배열	0	1	2	3	4	5

 

  2. 각 그래프의 연결 관계가 데이터로 들어왔을 때 이를 배열에 기록하면 다음과 같이 될 수 있습니다. 

index	0	1	2	3	4	5
parent 배열	1	2	2	3	1	3

 

1. find(&parent, 4)을 실행하면 다음과 같은 작업이 발생합니다.
2. parent[4]에 접근하여 1을 얻는다.
3. parent[1]에 접근하여 2를 얻는다.
4. parent[2]에 접근하여 2를 얻는다.
5. index와 value가 2로 같기 때문에 find함수는 2를 리턴하고 종료된다.
6. 즉, 4의 부모 노드는 2가 됩니다. (부모를 계속 거슬로 올라가며 최종 부모를 찾았음)

이제 Union 연산을 실행했을 때의 예시를 보여드리겠습니다.

union(&parent, 4, 5)를 실행하면 다음과 같은 작업이 발생합니다.

1. find(&parent, 4) 를 실행하여 4의 부모가 2라는 것을 확인
2. find(&parent, 5) 를 실행하여 5의 부모가 3이라는 것을 확인

둘 중 하나의 부모 노드의 부모를 다른쪽 부모 노드로 바꾸면 두 그래프가 연결되게 됩니다.

여기서는 5의 부모를 4의 부모로 바꾸어서 두 집합을 합치겠습니다.

(정확히는 5의 부모인 3의 parent 값을 4의 부모로 바꾸는 작업입니다.)

index	0	1	2	3	4	5
parent 배열	1	2	2	2	1	3

 

두 그래프가 합쳐져서 1개의 그래프가 된 모습

 

Union-Find 코드

func find(_parent: inout [Int], _ index: Int)-> Int{
  if parent[index] == index {
    return index
  }
  parent[index] = find(&parent, parent[idnex])
  return parent[index]
}

func union(_ parent: inout [Int], _ a: Int, _ b: Int) {
  let parentOfA = find(&parent, a)
  let parentOfB = find(&parent, b)

  if a < b {
    parent[parentOfB] = parentOfA
  }else {
    parent[parentOfA] = parentOfB
  }
}

 

find 는 부모를 찾는 함수

union을 부모를 합치는 함수

 

사용예시

fileprivate func solution(_ n:Int, _ costs:[[Int]]) -> Int {
    
    // 간선을 오름차순으로 정렬
    let costs = costs.sorted {
        $0[2] < $1[2]
    }
    var result = 0
    var parent = [Int]()
    
    // 자기 자신을 부모 노드로 설정하여 parent 배열 초기화
    for i in 0..<n {
        parent.append(i)
    }
    
    // 부모가 다르면 결과에 추가
    for cost in costs {
        let node1 = cost[0]
        let node2 = cost[1]
        if find(&parent, node1) != find(&parent, node2) {
            union(&parent, node1, node2)
            result += cost[2]
        }
    }
    
    return result
}

 

 

주의할점

find 함수를 구현하다가 이런 실수를 했다.

 func find(_ parent: inout [Int], _ index: Int) -> Int { // 부모번호 반환
        if parent[index] == index {
            return index
        }
        
        let parentNum = find(&parent, index)
        return parentNum
    }

 

어느부분이 잘못된지 보이는가.

우리는 parent내의 변수를 갱신해줘야하는데 단순히 값을 받고 return만 해주고 있다.

갱신과 반환 모두 하기위해 아래와같이 바뀌어야한다.

 

func find(_ parent: inout [Int], _ index: Int) -> Int { // 부모번호 반환
        if parent[index] == index {
            return index
        }
        
        parent[index] = find(&parent, parent[index])
        return parent[index]
    }

 

 

실제 사용 예시

import Foundation

func solution(_ n: Int, _ costs: [[Int]]) -> Int {
    
    // 가중치를 기준으로 오름차순 정렬
    let sortedLand = costs.sorted{ $0[2] < $1[2] }
    
    // 부모 배열 생성
    var parent = [Int]()
    
    for i in 0..<n{
        parent.append(i)
    }
    
    func find(_ parent: inout [Int], _ index: Int) -> Int { // 부모번호 반환
        if parent[index] == index {
            return index
        }
        
        parent[index] = find(&parent, parent[index])
        return parent[index]
    }
    
    func union(_ parent : inout [Int], _ a: Int, _ b: Int) {
        let parentOfA = find(&parent, a)
        let parentOfB = find(&parent, b)
        
        if parentOfA < parentOfB {
            parent[parentOfB] = parentOfA
        }else{
            parent[parentOfA] = parentOfB
        }
    }
    
    var result = 0
    
    for cost in sortedLand {
        let a = cost[0]
        let b = cost[1]
        let price = cost[2]
        if find(&parent,a) != find(&parent,b){
            union(&parent,a,b)
            result += price
        }
    }
    
    return result
}