한 편인지 물어보자냥! 유니온 파인드
안녕, 나 코딩냥이다냥! 오늘은 "얘랑 쟤가 같은 편이냥?" 을 아주 빠르게 답하는 자료구조를 배운다냥. 이름이 유니온 파인드라냥. 서로소 집합이라고도 한다냥.
친구 관계, 네트워크 연결, 그래프의 사이클 판별에 두루 쓰인다냥. 코드가 짧은데 강력하다냥.
오늘의 학습 목표
- 대표(루트) 로 집합을 구분하는 아이디어를 안다.
find와union을 만든다.- 경로 압축으로 빠르게 만든다.
- 크기를 관리해 큰 집합을 찾는다.
- 사이클 판별에 쓴다.
1단계 · 대표로 구분한다냥 (10분)
여러 개의 무리가 있다냥. "이 둘이 같은 무리냥?" 을 어떻게 빨리 답하냥? 각 무리마다 대표 한 명을 정해두면 된다냥. 대표가 같으면 같은 무리라냥.
비유로 이해하기 — 반 대표
두 학생이 같은 반인지 알고 싶다냥. 각자 자기 반 대표가 누구인지 물어보면 된다냥. 대표가 같으면 같은 반이라냥. 학생을 하나하나 비교할 필요가 없다냥.
유니온 파인드는 각 원소가 자기 대표로 가는 길(부모) 을 하나씩 들고 있는 거라냥. 부모를 따라 끝까지 올라가면 대표라냥.
parent = list(range(n + 1)) # 처음엔 자기 자신이 대표라냥처음에는 모두가 혼자라, 자기 자신이 대표라냥.
2단계 · find 와 union (12분)
두 가지 연산만 있으면 된다냥. find 는 대표를 찾고, union 은 두 무리를 합친다냥.
def find(x):
while parent[x] != x: # 자기가 대표가 아니면
x = parent[x] # 부모로 올라간다냥
return x부모가 자기 자신인 곳이 대표라냥. 거기까지 따라 올라간다냥.
def union(a, b):
ra, rb = find(a), find(b)
if ra != rb:
parent[rb] = ra # b의 대표를 a의 대표 밑으로냥두 무리의 대표끼리 이어붙인다냥. 원소 하나하나가 아니라 대표만 바꾸면 무리 전체가 합쳐진다냥.
같은 집합인지는 find 로 비교해야 한다냥.
if find(a) == find(b): # 맞다냥
if parent[a] == parent[b]: # 틀린다냥!parent[a] 는 바로 위 부모일 뿐, 대표가 아니라냥. 같은 무리여도 바로
위 부모는 다를 수 있다냥. 반드시 끝까지 올라간 대표(find)로 비교해야
한다냥.
오늘 1번 문제가 정확히 이 실수를 잡는다냥.
3단계 · 경로 압축 (12분)
find 를 그냥 두면 무리가 일자로 길게 늘어질 때 느려진다냥. 대표까지
올라가는 길이 길어지기 때문이라냥. 그런데 아주 간단한 요령으로 확 빨라진다냥.
비유로 이해하기 — 물어본 김에 지름길 알려주기
대표를 찾으러 부모를 타고 한참 올라갔다냥. 그럼 올라가면서 만난 애들한테 "대표는 저기야" 하고 바로 연결해주는 거라냥. 다음에 물으면 한 번에 대표로 간다냥.
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # 할아버지로 당긴다냥
x = parent[x]
return xparent[x] = parent[parent[x]] 한 줄이 전부라냥. 대표를 찾아 올라가면서
각 노드를 할아버지에 바로 붙인다냥. 그러면 트리가 점점 납작해진다냥.
이걸 경로 압축이라고 한다냥. 이 한 줄 덕에 find 가 거의 상수 시간이
된다냥. 유니온 파인드가 빠른 비결이라냥.
경로 압축이 없어도 답은 맞는다냥. 다만 큰 입력에서 느려질 뿐이라냥.
그래서 처음부터 넣는 습관을 들이자냥. 위 find 를 그냥 외워서 쓰면 된다냥.
4단계 · 크기를 세면서 합친다냥 (12분)
"가장 큰 무리에 몇 명이 있냥?" 같은 걸 물으면, 각 대표가 자기 무리의 크기를 들고 있게 하면 된다냥.
size = [1] * (n + 1) # 처음엔 다들 혼자니 1이라냥
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb:
return
if size[ra] < size[rb]: # 작은 쪽을 큰 쪽 밑에 붙인다냥
ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb] # 크기를 합친다냥대표 ra 밑으로 rb 를 붙이면, ra 의 무리 크기에 rb 의 크기를
더한다냥. 그러면 대표의 크기 = 그 무리의 크기가 항상 유지된다냥.
작은 무리를 큰 무리 밑에 붙이면(크기로 합치기) 트리가 덜 깊어져서 더 빨라진다냥. 경로 압축과 같이 쓰면 최강이라냥.
오늘 3번(가장 큰 무리)과 4번(친구 네트워크)이 이 크기를 쓴다냥. 특히 4번은
합칠 때마다 그 무리의 크기를 출력하니, size[find(a)] 를 그때그때
읽으면 된다냥.
5단계 · 사이클 판별 (10분)
유니온 파인드의 멋진 쓰임이라냥. 간선을 하나씩 추가하다가 사이클이 생기는 순간을 잡는 거라냥.
두 끝이 이미 같은 무리인 간선이 사이클을 만든다냥.
간선 a-b 를 추가하려는데 find(a) == find(b) 라면, 둘은 이미 다른 길로
이어져 있다냥. 여기에 간선을 하나 더 그으면 고리(사이클) 가 생긴다냥.
ra, rb = find(a), find(b)
if ra == rb:
# 이 간선이 사이클을 만든다냥!
else:
parent[rb] = ra # 아니면 합친다냥간선마다 이렇게 한다냥.
- 두 끝의 대표를
find로 구한다 - 대표가 같으면 → 사이클이라냥 (합치지 않는다)
- 다르면 → 합친다
오늘 5번 문제가 이거라냥. 처음 사이클이 생기는 간선을 찾는다냥. 이 아이디어는 다음 장의 최소 신장 트리에서 그대로 쓰인다냥.
오늘 배운 내용 정리
먼저 스스로 답해보고, "정답 보기"를 눌러서 맞는지 확인해보자냥!
이제 직접 풀어볼 차례다냥
오늘 문제는 다섯 개라냥. 1번은 기본 연산, 2번 그룹 개수, 3번 가장 큰 그룹, 4번 친구 네트워크(합칠 때마다 크기), 5번 사이클 판별이라냥.
find 와 union 을 한 번 제대로 짜두면 나머지는 거의 그대로 쓴다냥.
1번의 parent 비교 함정만 조심하자냥. 가보자냥~