99클럽 코테 스터디 6일차 TIL + MST

 

오늘의 문제

https://www.acmicpc.net/problem/6497

 

MST

MST는 minimum spanning tree = 최소 신장 트리의 약자이다.

 

최소 신장 트리에서 신장이라는 단어가 생소할 것이다. 

 

최소 신장 트리의 의미는 그래프에서 모든 정점을 포함하는데 가중치의 합이 최소로 연결된 사이클이 없는 트리를 의미한다. 

 

즉 모든 정점들이 연결되어 있어야 하는데 최소 비용으로 연결되어 있어야 하고 사이클이 없어야 하는 경우에 MST를 만드는 것이다. 

 

MST를 만드는 방법은 2가지가 있다고 한다. 

• Kruskal 알고리즘
• Prim 알고리즘

 

두 알고리즘에 대해 간단히 설명하면 아래와 같다. 

 

Kruskal 알고리즘

• 가장 비용이 작은 간선을 선택해가는 알고리즘
• 가중치 순으로 간선들을 오름차순 정렬
• 가중치가 가장 작은 간선을 선택
• 사이클을 이루는지 검사
• 사이클을 이루지 않는다면 MST에 간선 추가
• 반복

 

Prim 알고리즘

• 인접한 정점 중 정점까지의 가장 비용이 작은 간선을 선택해가는 알고리즘
• 시작 정점을 선택해 MST에 추가
• 시작 정점의 인접한 정점 중 간선의 가중치가 가장 작은 정점 선택
• 반복

 

추후에 두 알고리즘 모두 각각 공부해서 정리해보겠다. 

 

참고 자료

• https://ansohxxn.github.io/algorithm/mst/
• https://ggjjdiary.tistory.com/49

 

회고

딱 MST를 만드는 문제였던 것 같다. 

 

prim 알고리즘으로 풀려고 시도했다. 

 

그런데 아직 prim 알고리즘이 완벽히 숙지 되지 않아서 그런지 틀린 것 같다. 

 

그리고 우선 순위 큐를 사용하지 않았는데 노드 개수가 200000이니 시간 복잡도 O(n^2)로 시간 초과가 날 것 같다. 

 

kruskal 알고리즘과 union-find 방식을 공부해서 풀어봐야 할 것 같다. 

 

그리고 절약할 수 있는 최대 비용을 출력하는 것도 잊지 말아야 할 것 같다. 

 

전체 비용에서 MST를 만드는데 필요한 비용을 빼는 것이 답일 것 같다.