유니온 파인드 알고리즘이란?
그래프 알고리즘의 일종으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.
def find(x,parent):
if x != parent[x]:
parent[x] = find(parent[x],parent)
return parent[x]
def union(a,b,parent):
a = find(a,parent)
b = find(b.parent)
if a < b:
parent[b] = a
else:
parent[a] = b특정 노드의 루트 노드를 찾는 find함수와 두 노드를 합치는 union 함수로 이루어져있다.
find 함수는 재귀함수를 이용해 특정 노드의 루트 노드가 나올때까지(자기 자신이 부모일때까지) 반복해서 찾아내고
union함수는 find 함수를 이용해 주어진 두 노드의 루트 노드를 찾은 후 작은 수 큰 수의 부모 노드가 되도록 변경한다.
그래프의 간선이 생길 시 union함수를 이용해 두 노드를 합치는 과정을 반복한다면
특정한 두개의 노드가 주어졌을때 find 함수를 이용해 두 그래프의 루트 노드를 비교하고 같은 그래프에 속하는지 알 수 있다.
최소 신장 트리(MST, Minimum Spanning Tree)란?
그래프의 일부 간선을 선택해 그래프 내의 모든 정점을 최소 비용으로 연결해낸 트리이다.
크루스칼 알고리즘이 가장 대표적인 구현방법인데 실제로는 유니온 파인드 알고리즘을 사용해서 쉽게 구현할 수 있다.
크루스칼 알고리즘은 그리디 알고리즘의 일종으로 사이클이 발생하지 않는 최소 가중치의 간선만을 골라나가 연결하는 방법이다.
간선을 연결할때 union 함수를 사용한다면 특정한 간선을 연결하면 사이클이 발생하는지를 find 함수를 통해 알아낼 수 있다.
https://www.acmicpc.net/problem/1197
1197번: 최소 스패닝 트리
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이
www.acmicpc.net
import sys,heapq
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a,b):
a = find(a)
b = find(b)
if a < b:
parent[b] = a
elif b < a:
parent[a] = b
v,e = map(int,sys.stdin.readline().strip().split())
parent = list(range(0,v+1))
route = []
ans = 0
for i in range(e):
a,b,c = map(int,sys.stdin.readline().strip().split())
heapq.heappush(route,(c,a,b))
while route:
c,a,b = heapq.heappop(route)
if find(a) != find(b):
ans += c
union(a,b)
print(ans)최소비용의 간선을 구하는 데에는 힙 자료구조를 사용하면 빠르게 구할 수 있다.
위상 정렬 알고리즘이란?
순서가 정해진 작업을 수행하기 위해 그래프를 이용해 순서를 결정하는 알고리즘이다.
가장 많이 사용하는 방법은 큐를 이용한 방법이다.
1. 그래프의 두 정점이 연결된 경우 도착지점의 진입차수를 1개씩 증가시킨다.
2. 진입차수가 0인 정점을 큐에 삽입한다.
3. 큐에서 원소를 하나씩 꺼내며 연결된 간선을 제거한다.(연결된 정점의 진입차수를 1개씩 감소시킨다)
4. 진입차수가 0이 된 정점을 새롭게 큐에 삽입한다.
5. 큐가 빌 때까지 3-4의 과정을 반복한다.
https://www.acmicpc.net/problem/2252
2252번: 줄 세우기
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의
www.acmicpc.net
import sys
from collections import deque
n,m = map(int,sys.stdin.readline().strip().split())
indegree = [0]*(n+1) #진입차수 배열
graph = [[] for _ in range(n+1)]
que = deque()
for i in range(m):
a,b = map(int,sys.stdin.readline().strip().split())
graph[a].append(b)
indegree[b] += 1
for i in range(1,n+1):
if indegree[i] == 0:
que.append(i)
while que:
now = que.popleft()
print(now,end = " ")
for nextPoint in graph[now]:
indegree[nextPoint] -= 1
if indegree[nextPoint] == 0:
que.append(nextPoint)
'백준 플레를 향해서' 카테고리의 다른 글
| 플레찍었으니 정리해보는 알고리즘 노트 6 - LIS(최장 증가 부분 수열) (0) | 2023.02.09 |
|---|---|
| 플레찍었으니 정리해보는 알고리즘 노트 4 - 세그먼트 트리 (0) | 2023.02.07 |
| 플레찍었으니 정리해보는 알고리즘 노트 3- GCD, 유클리드 호제법,오일러 피 함수 (0) | 2023.02.06 |
| 플레찍었으니 정리해보는 알고리즘 노트 2 - 중간에서 만나기, 투 포인터 (0) | 2023.02.06 |
| 플레찍었으니 정리해보는 알고리즘 노트 1 - 이진탐색 (0) | 2023.02.05 |