크루스칼 알고리즘과 Find-Union 알고리즘 Python

백준에서 그래프 관련 문제 중 어떤 노드에서 모든 노드를 거쳐 돌아왔을 때의 비용을 구하는 문제를 풀던 과정에 알게 된 크루스칼 알고리즘, Find-Union 알고리즘에 대해 소개한다.

내가 알고 있는 그래프 알고리즘 중 최소 비용을 구하는 알고리즘 중 하나는 다익스트라 알고리즘이 있는데, 해당 알고리즘과 먼저 비교해본 뒤, 크루스칼 알고리즘과 함께 크루스칼 알고리즘 구현 시 사용되는 Union-Find 알고리즘에 대해서도 설명한다. 

다익스트라 알고리즘과 크루스칼 알고리즘의 차이점

적용 대상

• 다익스트라 : 주로 가중치가 있는 방향 그래프에서 사용되며, 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제에 적용
• 크루스칼 : 주로 가중치가 있는 무방향 그래프에서 사용. 최소 스패닝 트리(최소 비용 신장 트리라고도 함)를 구하는 문제에 적용

목적

• 다익스트라 : 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 것
• 크루스칼 : 모든 정점을 포함하면서 사이클이 없고 가중치의 합이 최소인 최소 비용 신장 트리를 구하는 것이 목적

작동 방식

• 다익스트라 : 현재 거리에서 각 정점까지의 최단 거리를 유지하면서, 방문하지 않은 정점 중에서 가장 최단 거리가 짧은 정점을 선택하여 최단 거리를 갱신, 이 과정에서 모든 정점을 방문할 때까지 반복
• 크루스칼 : 그리디(탐욕) 알고리즘으로 간선의 가중치를 기준으로 최소 스패닝 트리를 구성. 간선들을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 최소 비용 신장 트리를 구성

 

크루스칼 알고리즘

먼저 크루스칼 알고리즘은 탐욕적인 방법을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 알고리즘이다. 따라서 결정을 해야 할 때, 당시에 가장 좋다고 생각되는 것을 채택함으로써 최종적인 해답을 만들어가는 것이 목표다.

1. 동작 과정은 그래프의 간선들을 가중치의 오름차순으로 정렬하고
2. 정렬된 간선들을 하나씩 선택하며 사이클을 형성하지 않은 간선을 선택한다. (Find 알고리즘 활용)
3. 선택한 간선을 최소 스패닝 트리의 집합에 추가한다.
4. 모든 정점이 포함될 때까지 2,3 단계를 반복한다.

  total = 0 # 최소 비용
  # 해당 arr는 [시작점, 도착점, 가중치]를 요소로 갖는 배열
  arr.sort(key= lambda x : x[2]) # 1. 가중치 오름차순 정렬
  
  for s,e,w in arr : # s,e,w 순서대로 시작점, 도착점, 가중치
    if find(s) == find(e) : continue # 같은 사이클(같은 원소를 root로 하는 경우)에 포함되면 패스
    total += w 
    union(s,e) # 같은 사이클로 합침
    
  print(total)

 

Union-Find 알고리즘

Union-Find 알고리즘은 여러 개의 원소들이 존재할 때, 이들을 그룹으로 관리하며 그룹 간의 연결성을 판별하는 알고리즘이다. 주로 상호 배타적인 집합을 표현하고 관리하기 위해 사용한다. 그리고 해당 알고리즘은 Union | Find 알고리즘으로 따로 구분된다.

Find 연산

• Find 연산은 주어진 원소가 어떤 그룹에 속해 있는지를 판별한다.
• 원소 x가 주어졌을 때 x가 속한 그룹의 대표 원소(또는 루트 원소)를 반환한다.
• 대표 원소는 보통 그룹을 대표하는 원소로 선택되며, 그룹 내 모든 원소들은 같은 대표 원소를 가지게 된다.
• Find 연산은 그룹의 연결성을 확인하거나 원소의 소속 그룹을 판별하는데 사용된다.

Union 연산

• Union 연산은 두 개의 그룹을 하나로 합치는 연산이다.
• 주어진 두 원소를 각각 속한 그룹의 대표 원소로 찾아서, 하나의 그룹으로 합친다.
• Union 연산을 통해 그룹들이 서로 연결되거나 합쳐지며, 그룹 간의 관계를 갱신한다.

  root = {}
  # 처음 각 원소들은 자기 자신을 root 원소로 가짐
  for i in range(1, n+1) :
    root[i] = i 
  
  # find 연산은 재귀적인 방법을 통해 해당 원소의 root원소를 반환
  def find(v) :
    if root[v] == v : return v
    else : 
      root[v] = find(root[v])
      return root[v]
    
  # union 연산은 a원소를 b원소에 포함시킴
  def union(a,b) :
    x,y = find(a), find(b)
    root[y] = x