[알고리즘] 유니온 파인드(Union-find) 알고리즘

[알고리즘] 유니온 파인드(Union-find) 알고리즘

• 유니온 파인드 알고리즘: 서로소 집합, 상호배타적 집합(Disjoint-Set)알고리즘이라고도 불린다. 여러 노드가 있을 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

• 입력 예시

  6 4
  1 4
  2 3
  2 4
  5 6

• 경로 압축 기법을 사용하지 않은 풀이

  # 특정 원소가 속한 집합 찾기
  def find_parent(parent, x):
      if parent[x] != x:
          return find_parent(parent, parent[x])
      return x
  
  # 두 원소가 속한 집합 합치기
  def union_parent(parent, a, b):
      a = find_parent(parent, a)
      b = find_parent(parent, b)
      if a < b:
          parent[b] = a
      else:
          parent[a] = b
  
  # 노드의 개수와 간선(union 연산)의 개수 입력 받기
  v, e = map(int, input().split())
  parent = [0] * (v+1)
  
  # 부모 테이블상에서, 부모를 자기 자신으로 초기화
  for i in range(1, v+1):
      parent[i] = i
  
  # union 연산을 각각 수행
  for i in range(e):
      a, b = map(int, input().split())
      union_parent(parent, a, b)
  
  print("각 원소가 속한 집합: ", end = '')
  for i in range(1, v+1):
      print(find_parent(parent, i), end = ' ')
  
  print()
  
  print("부모 테이블: ", end = '')
  for i in range(1, v+1):
      print(parent[i], end = ' ')

• 출력

  각 원소가 속한 집합: 1 1 1 1 5 5
  부모 테이블: 1 1 2 1 5 5 

---

• 경로 압축 기법을 사용한 풀이

  def find_parent(parent, x):
      if parent[x] != x:
          parent[x] = find_parent(parent, parent[x])
      return parent[x]
  
  def union_parent(parent, a, b):
      a = find_parent(parent, a)
      b = find_parent(parent, b)
      if a < b:
          parent[b] = a
      else:
          parent[a] = b
  
  v, e = map(int, input().split())
  parent = [0] * (v+1)
  
  for i in range(1, v+1):
      parent[i] = i
  
  for i in range(e):
      a, b = map(int, input().split())
      union_parent(parent, a, b)
  
  print("각 원소가 속한 집합: ", end = '')
  for i in range(1, v+1):
      print(find_parent(parent, i), end = ' ')
  
  print()
  
  print("부모 테이블: ", end = '')
  for i in range(1, v+1):
      print(parent[i], end = ' ')

• 출력

  각 원소가 속한 집합: 1 1 1 1 5 5
  부모 테이블: 1 1 1 1 5 5 

---

• 유니온 파인드를 이용한 사이클 판별

  • 입력 예시

    3 3
    1 2
    1 3
    2 3

  • 소스코드

    # 서로소 집합은 무방향 그래프 내에서의 사이클 판별 시 사용 가능
    # 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별 가능
    def find_parent(parent, x):
        if parent[x] != x:
            parent[x] = find_parent(parent, parent[x])
        return parent[x]
    
    def union_parent(parent, a, b):
        a = find_parent(parent, a)
        b = find_parent(parent, b)
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
    
    v, e = map(int, input().split())
    parent = [0] * (v+1)
    
    for i in range(1, v+1):
        parent[i] = i
    
    cycle = False
    
    for i in range(e):
        a, b = map(int, input().split())
        # 사이클이 발생한 경우 종료
        if find_parent(parent, a) == find_parent(parent, b):
            cycle = True
            break
        else:
            union_parent(parent, a, b)
    
    if cycle:
        print("사이클이 발생했습니다.")
    else:
        print("사이클이 발생하지 않았습니다.")

  • 결과

    사이클이 발생했습니다.