오랜만에 문제풀다 하나씩
오늘은 union find disjoint set 알고리즘을 공부할 차례
보스가 -1이고 보스랑 연결되어 있는 조직원 찾고,
그 조직원과 보스가 묶인 부분집합이 몇 개있는지 찾는 문제다
https://brownbears.tistory.com/460
union find(disjoint-set)의 핵심은 아래 3가지.
1. 초기화 : N 개의 원소가 각각의 집합에 포함되어 있도록 초기화
2. Union 연산 : 두 원소 a, b 가 주어질 때, 이들이 속한 두 집합을 하나로 합침
3. Find 연산 : 어떤 원소 a 가 주어질 때, 이 원소가 속한 집합을 반환
Union-Find의 사용 예시
전체 집합이 있을 때 구성 원소들이 겹치지 않도록 분할(아래 참고*)하는 데 자주 사용된다.
Kruskal MST 알고리즘에서 새로 추가할 간선의 양끝 정점이 같은 집합에 속해 있는지(사이클 형성 여부 확인)에 대해 검사하는 경우
초기에 {0}, {1}, {2}, … {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려는 경우
집합의 표현-백준1717번
어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 가입한 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하는 경우
친구 네트워크-백준4195번
https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html
기본적인 find, union 알고리즘 함수
# https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html 를 c->python화
root = (x for x in range(MAX_SIZE)
# find()는 재귀다
def find(x):
if root[x] == x:
return x
else:
return find(root[x])
def union(x, y):
x = find(x)
y = find(y)
# 자식 인덱스 값을 부모로 업데이트해준다
root[y] = x
경로 압축 알고리즘
root = [x for x in range(100)]
def find(x):
if root[x] == x:
return x
else:
return root[x] = find(root[x])
# find를 수행하면서 만난 모든 부모 노드를 루트 노드로 바꿔준다
'파이썬 > 문제풀다 하나씩' 카테고리의 다른 글
백준 5430번 AC deque and reverse 시간초과 주의 (0) | 2021.07.23 |
---|---|
백준 3190번 뱀 파이썬 이중배열 board만들고 값 바꾸면서 디큐로 풀기 (0) | 2021.07.23 |
readme 고민 중 표로 할까말까 (0) | 2021.07.22 |
프로그래머스 소수 찾기 dfs 완전탐색 문제 (0) | 2021.07.19 |
백준 파이썬 탑 stack 문제 (0) | 2021.07.19 |
프로그래머스 K번째수 Lambda and map() (0) | 2021.07.19 |
프로그래머스 큰 수 만들기 파이썬 (백준도 있음) (0) | 2021.07.16 |
백준 6198 옥상정원 (0) | 2021.07.16 |