프림 알고리즘1 [알고리즘] 9-7 원더랜드 - 프림 알고리즘, 최소 신장 트리, Greedy (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 복습할 때 개인적으로 참고하기위해 풀이 코드를 정리하고 있습니다. 문제 링크 : https://cote.inflearn.com/contest/10/problem/09-07 프림 알고리즘(Prim Algorithm) 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법 동작 과정 시작 정점을 최소 신장 트리 집합에 포함한다. 집합에 포함된 정점과 연결된 정점들 중에 최소 비용으로 연결된 정점을 선택하여 연결하여 집합을 확장한다. (단, 회로를 형성하는 이미 집합에 포함된 정점끼리 연결하는 것은 제외) 2번 과정을 최소 신장 트리가 완성될 때까지 반복한다. 신장 트리 : 그래프의 모든 정점이 연결되어있고, 회로가.. 2021. 6. 30. 이전 1 다음