최소신장트리 자바1 [Java, 알고리즘, 최소신장 트리] - 이것이 코딩테스트다 :: 도시 분할 계획 문제에서 요구사항은 1. 마을을 연결하는 도로중에서 최소 비용으로 연결 되도록 연결하고 필요 없는 도로는 제거 2. 모든 마을이 연결되어 있어야 된다. 3. 2개의 분리된 마을로 분할 요구사항 1, 2번까지만 보면 최소 신장 트리를 구하면 된다. 3번 요구사항은 어떻게 풀어야 할까? 크루스칼 알고리즘은 가중치를 오름차순으로 정렬하여 최소 비용으로 모든 노드들이 싸이클 없이 연결되는 경로를 구할 수 있다. 여기서 최대 비용의 간선을 삭제하면 최소 신장 트리가 2개로 분리 될 것이다. 예를 들면, 가중치가 가장 큰 9 간선을 제거하면 그림 처럼 2개의 트리로 나뉘어 진다. package com.algorithm.graph; import java.io.BufferedReader; import java.io.I.. 2021. 3. 16. 이전 1 다음
