[그래프] 그래프 알고리즘 공부하기

삼성 알고리즘에서 배웠던 것들 조금 고급이나 많이 접해보지 못한 것들 알고리즘이랑 자료구조들 공부해봅시다.

그래프란?

그래프는 노드랑 간선으로 이루어진 자료구조이고 순환 구조가 없는 걸 트리 자료구조라고 할 수 있음.

간선에 방향이 존재하는지 여부가 중요하니까 잘 파악할 것. 기본적인 DFS나 BFS는 많이 접해봤으니까 덜 접해본 알고리즘들을 공부해보자.

 

서로소 집합 (Union-Find)

오늘 풀었던 문제에서도 나왔는데 집합을 이루는지 확인하고 하나의 집합으로 만들 수 있는 그런 알고리즘.

• Union 연산 (합집합)
  • 어떤 두 원소 a, b에 대해서 각 원소가 속한 집합을 하나로 합치는 연산임.

def union(a, b):
	parentA = find(a)
    parentB = find(b)
    
    if parentA == parentB: return;
    
    if parentA > parentB:
    	parent[parentA] = parentB
    else :
    	parent[parentB] = parentA

파이썬 코드라기 보단 수도코드라고 생각하자.

• Find 연산
  • 어떤 원소 a에 대해서 a가 속한 집합을 반환.

def find(a):
    if parent[a] == a:
    	return a;
    return parent[a] = find(parent[a]);

이 연산들을 이용해서 그래프의 사이클 여부를 파악하거나 링크 건 문제에서처럼 어떤 집합에 속하는지 여부를 파악함으로써 최적의 연산을 수행할 수 있음.

위상정렬 (Topological Sort)

예를 들면 특정 순서로 강의를 들어야 하는 경우 같은 상황에서 위상정렬을 이용할 수 있는데 위상 정렬은 위상에 따라 먼저 처리되어야 하는 노드가 있는 경우에 쓰일 수 있음.

• DAG (비순환 방향 그래프)에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 것
• 위상정렬은 각 정점을 우선순위에 따라 배치 한 것
• 일반적으로 위상정렬의 결과는 유일하지 않음.

def topological_sort():
	q.add(0인 애들 넣기)
	while !q.isEmpty():
    		now = q.remove();
        	print(now)
    		for n in adj[now]:
	        	priority[n] -= 1
    
if __name__ == __main__:
	for _ in range(n):
    	preNode, afterNode = input()
        priority[afterNode] += 1 // 진입차수를 높이는 것.
        adj[preNode].add(afterNode)
        
    topological_sort()

대략 이런 느낌으로 차수가 0인 애들 부터 쭈욱 돌면서 차수 줄여주고 요런 느낌.

최소 신장 트리 (MST / Minimum Spanning Tree)

앞에서 순환 구조가 없으면 트리라고 했응께 공부해봅시다.

간단하게 순환 구조가 없이 최소한의 가중치의 합으로 트리를 구성하면 된다. -> 트리라 함은 모든 노드가 도달할 수 있는 경로가 존재해야죠.

그냥 모든 간선 다 가지고 있고 이걸 가중치로 정렬 -> 간선 하나씩 뽑으면서 이걸 넣으면 순환구조가 생기는지 여부를 파악하는데 이 때 위에서 공부한 서로소 집합을 이용하면 되겠죠. 요 방법이 크루스칼 알고리즘을 이용해서 푸는 방식이고 프림 알고리즘을 이용하면 최소 힙을 이용해서 풀면 되는데 간선이 많으면 프림, 그게 아니면 크루스칼 이용하면 될 듯.

---

마무리

나머지 LCA, 트리에서 조상-자손 관계 판별하는 거, 단절점, 최단 경로 (다익스트라, 벨만-포드, 플로이드 워셜)은 다음시간에 공부해보자.