[Algorithm] Union Find (유니온 파인드) - Python

문지은·2023년 4월 4일
0

Algorithm with Python

목록 보기
3/19
post-thumbnail
post-custom-banner

🎀 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)

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

profile
코드로 꿈을 펼치는 개발자의 이야기, 노력과 열정이 가득한 곳 🌈
post-custom-banner

0개의 댓글