🎀 Union Find

• 노드를 합치고(union) 부모를 찾아(find) 서로소 집합(disjoint set)을 찾아내는 알고리즘
• 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조
• 다수의 노드들 중에 연결된 노드를 찾거나 노드들을 합칠때 사용

⭐ 구현하기

• 5개의 노드 (A, B, C, D, E) 가 있고 아래와 같이 그룹화 시키고 싶다고 가정해보자.
  • A-B, D-E, B-E, B-D, E-F
• 다음 세 단계를 거쳐 Union Find를 구현할 수 있다.

테이블 초기화

• N 개의 노드가 각각의 집합에 포함되어 있도록 (자신이 루트 노드이도록) 초기화 한다.
• 테이블에 저장된 값이 루트 노드를 나타내며, 0이 저장되어 있으면 자신이 루트 노드이다.
  

코드 작성

arr = [0]*200

Union 연산

• 두 원소 a, b 가 주어질 때, 이들이 속한 두 집합을 하나로 합침
  • 각각의 루트 노드를 찾는다. (테이블에 저장된 값)
  • 두 원소의 루트노드가 같다면 이미 같은 그룹이다.
  • 다르다면 더 b 보스에 a 보스를 각인한다.
• A 와 B 를 Union 연산하면 아래와 같이 저장된다.
  
• 가정한 A-B, D-E, B-E, B-D, E-F 를 전부 union 하면 아래와 같이 저장된다.
  

코드 작성

def setunion(a, b):
	# boss 찾기
    fa, fb = findboss(a), findboss(b)
    if fa == fb:  # 각각의 보스가 같으면 이미 같은 그룹
        return 
    arr[ord(fb)] = fa  # 다르면 b 보스에 a 보스 각인

Find 연산

• 어떤 원소 a 가 주어질 때, 이 원소가 속한 집합을 반환
  • 자기 자신이 boss라면(테이블에 저장된 값이 0이라면) 자기 자신 반환
  • 아니라면 자신의 boss의 boss 찾기

코드 작성

def findboss(member):
    if arr[ord(member)] == 0:  # 자기 자신이 boss 라면
        return member  # 자기 자신 반환
    # 아니라면 최종 boss 찾기
    ret = findboss(arr[ord(member)])
    return ret

📍 최종 코드

arr = [0]*200

# 보스 찾기 
def findboss(member):
    if arr[ord(member)] == 0:  # 자기 자신이 boss 라면
        return member
    ret = findboss(arr[ord(member)])
    return ret

# 그룹화
def setunion(a, b):
    fa, fb = findboss(a), findboss(b)
    if fa == fb:  # 각각의 보스가 같으면 이미 같은 그룹
        return 
    arr[ord(fb)] = fa  # 다르면 b 보스에 a 보스 각인

setunion('A', 'B')
setunion('D', 'E')
setunion('B', 'E')
setunion('B', 'D')
setunion('E', 'F')

🔍 문제점

• 위 코드를 사용하여 루트노드를 찾을 때는 한가지 문제점이 있다.
• 루트노드가 아래와 같이 저장될 때 E의 루트 노드를 찾으려면 E -> D -> A 와 같이 비 효율적으로 찾아야 한다.
  

코드 개선하기 - 경로 단축

• 이러한 문제점을 개선하기 위해서 find 함수의 리턴값을 수정하여 경로를 단축시킬 수 있다.

def findboss(member):
    if arr[ord(member)] == 0:
        return member
    ret = findboss(arr[ord(member)])
    # 경로 단축
    arr[ord(member)] = ret
    return ret

• 코드를 수정하면 테이블 값이 아래와 같이 변경된다.
  

✔️ 활용 : cycle 여부 판단하기

• Union Find를 활용하여 양방향 그래프에서 cycle 여부를 판단할 수 있다.
• 각 간선의 두 노드의 루트 노드를 확인한다.
  • 루트노드가 서로 다르면 union 연산 실행
  • 루트노드가 서로 같으면 cycle 발생한 것

## 양방향 그래프에서 cycle 발생 여부 확인 
arr = [0]*200

def findboss(member):
    if arr[ord(member)] == 0:
        return member
    ret = findboss(arr[ord(member)])
    # 경로 단축
    arr[ord(member)] = ret
    return ret

def setunion(a, b):
    fa, fb = findboss(a), findboss(b)
    # boss 같으면 1 리턴
    if fa == fb:
        return 1
    arr[ord(fb)] = fa

# N 개의 간선 정보 입력
N = int(input())
edge = []  # 간선 정보 저장할 리스트
for _ in range(N):
    edge.append(input().split())


# cycle 발생 여부 출력
answer = 'cycle 미발생'
for i in range(N):
    a, b = edge[i]
    # boss 같으면 cycle 발생
    if setunion(a, b):
        answer = 'cycle 발생'

print(answer)

댓글과 좋아요 그리고 의견 감사합니다. ♥️