개발일지

개념 MST란 Minimun Spanning Tree의 약어로 최소 신장트리를 뜻한다. => 신장트리 중에서 가중치의 합이 최소인 신장트리를 구하는 것 => 신장트리 : Cycle이 없는 그래프 Prim Heap을 이용하여 MST를 갱신하며 구하는 알고리즘 작동원리 1. 시작노드를 우선순위 큐에 PUSH한다. 2. 우선순위 큐에서 노드를 POP한다. 3. 체크되지 않은 노드라면 WEIGHT 값만 큼 RESULT에 더하고 갈 수 있는 노드중 체크되지 않은 노드를 우선순위 큐에 PUSH한다. 4. 2 ~ 3을 우선순위 큐가 EMPTY일 때까지 반복한다. 시간복잡도 O(ElogV) 문제 13418 학교 탐방하기 www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표..