Gi-Log

문제: SW Expert Academy 1251 하나로 "섬이나 도시, 컴퓨터 등등 어떤 정점들을 모두 잇는 최소 경로가 필요하다!"라는 문제가 나오면 십중팔구 최소 신장 트리(MST) 문제이다. 이 문제 또한 크루스칼 알고리즘을 적용하여 MST를 생성해서 풀 수 있는 문제였다. 본 블로그에서 몇 번 설명을 진행한 풀이가 있는데, 크루스칼 알고리즘을 간단히 설명하면 다음과 같다. 1. 어떤 노드들을 잇는 간선들을, 그 비용을 기준으로 오름차순 정렬한다. 2. 가장 비용이 적은 간선부터 연결을 시작한다. 3. 이 때, 간선을 연결했을 때 싸이클이 발생하게 된다면 해당 간선은 연결하지 않고 건너 뛴다. 위 알고리즘 구현을 위해서는 간선 정보를 어떤 컨테이너에 잘 담고, 정렬할 수 있어야한다. 그리고 싸이클 ..