최소 신장 트리, MST(Minimum Spanning Tree)

[Taehyeon-Kim]

유니온-파인드(Union-find) 자료구조

• 크루스칼 알고리즘 구현 시 사용
• 그래프 사이클 탐지 시 사용

find 연산

func findParent(_ x: Int) -> Int {
  if p[x] == x { return x }
  p[x] = findParent(p[x])
  return p[x]
}

union 연산

func union(_ u: Int, _ v: Int) -> Bool {
  let u = findParent(u)
  let v = findParent(v)
  if u == v { return false }
  if u < v { p[v] = u }
  else { p[u] = v }
  return true
}

• 부모 노드, 루트 노드가 같다는 것은 union x, 즉 합칠 수 없다는 의미(사이클이 생긴다는 의미)

최초 부모 노드 초기화

var p = [Int]()
for i in 0..<n+1 {
  p.append(i)
}

크루스칼(Kruskcal) 알고리즘

• 간선의 비용이 작은 것부터 선택해나가야 하기 때문에 최초에 정렬을 한 번 해주고 시작한다. 이 때, 튜플 자료구조를 사용하게 된다.
• 간선을 V-1개 선택할때까지 반복하다가, V-1개가 되는 순간 종료한다.

func kruskcal() -> Int {
  var (ret, edges) = (0, 0)

  for (cost, u, v) in tuple {
    // 합칠 수 있다 = 사이클 x = 서로소
    if union(u, v) {
      ret += cost
      edges += 1
      // vertex - 1 까지 반복 가능
      if edges == n - 1 {
        return ret
      }
    }
  }
  return -1
}

전체코드

func input() -> (p: [Int], tuple: [(Int, Int, Int)], v: Int, e: Int) {
    let ve = readLine()!.split(separator: " ").compactMap {Int(String($0))}
    let (v, e) = (ve[0], ve[1])

    // 1) 튜플을 만든다.
    // - (가중치, 정점1, 정점2)
    var tuple = [(Int, Int, Int)]()
    for _ in 0..<e {
        let line = readLine()!.split(separator: " ").compactMap {Int(String($0))}
        let (a, b, c) = (line[0], line[1], line[2])
        tuple.append((c, a, b))
    }

    // 2) 튜플을 가중치 기준으로 오름차순 정렬한다.
    // - 작은 값부터 더해나가기 위함
    tuple = tuple.sorted(by: { $0.0 < $1.0 })
  
    // 3) 부모 노드 배열 초기화
    var p = [Int]()
    for i in 0..<v+1 {
        p.append(i)
    }
    
    return (p, tuple, v, e)
}

func kruskcal() -> Int {
    var (p, tuple, V, _) = input()

    // 4) find 연산
    func findParent(_ x: Int) -> Int {
        if p[x] == x { return x }
        p[x] = findParent(p[x])
        return p[x]
    }
    
    // 5) union 연산
    // - Bool 타입을 리턴해서 사이클 여부를 판단한다.
    func union(_ u: Int, _ v: Int) -> Bool {
        let u = findParent(u)
        let v = findParent(v)
        
        if u == v { return false }
        if u < v { p[v] = u }
        else { p[u] = v }
        return true
    }
    
    // 6) 가중치 합, 간선의 개수 -> ans, cnt
    // cnt(간선의 개수)가 (정점의 개수 - 1) 일 때 연산을 마친다.
    var (ans, cnt) = (0, 0)
    for (cost, u, v) in tuple {
        if union(u, v) {
            cnt += 1
            ans += cost
            if cnt == V - 1 {
                return ans
            }
        }
    }
    return ans
}

print(kruskcal())

[Taehyeon-Kim]

• boj 1197 최소 스패닝 트리 (기본꼴, 연습문제)
• boj 1922 네트워크 연결