어흥

문제링크: www.hackerrank.com/challenges/kruskalmstrsub/problem Kruskal (MST): Really Special Subtree | HackerRank Learn to use the Kruskal's algorithm ! www.hackerrank.com 1. 주의할 점 - 간선의 가중치가 같다면 각 Node의 합이 작은것을 우선시한다 - Make_union() 함수에서 부모를 잘 갱신하도록 한다 2. 구현 - 입력받는 모든 간선에 대한 정보를 우선순위큐 PQ에 넣는다 - PQ에서 꺼낸 간선에서 양 끝점이 만약 같은 집합이 아니라면 Make_union()함수를 통해 이어주며 Result에는 가중치만큼 더하며 Cnt++를 통해 MST의 경우 Node의 개수-1만..

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - A 지점부터 B지점까지(A!=B)의 거리를 저장하는 2차배열을 생성할 필요가 없다(Long 타입으로 최대 1000*1000 생성시 메모리 손해) - List를 이용해서 구현한다 - 소숫점 첫째자리에서 올림하는 경우는 최종단계에서만 1번 진행한다. - 그래프 내에 간선의 수가 적다면 Kruskal이, 간선이 많다면 Prim이 적절한 알고리즘이다 2. 구현 [Kruska..