Kruscal1 백준 4386 자바 - 별자리 만들기 (BOJ 4386 JAVA) 문제 : boj4386 1. 모든 별을 이어야하고, 최소 비용을 구해야 한다. 따라서 N개의 정점(별)에 대해 이은 간선이 N-1개(모든 정점을 포함하려면 최소 N-1개의 간선이 필요하고, 최소비용을 위해서는 거기서 하나라도 간선이 추가되선 안되므로) 이어야만 모든 별을 이으면서 최소 비용이 가능하다. 따라서 Spanning Tree를 구성해야 하고, 최소 비용이어야 하므로 MST (Minimum Spanning Tree)를 구하는 문제임을 알 수 있다. 후보군이 될 간선은 N개에 대해 다른 N-1개 모두로의 간선이므로 간선은 총 N*(N-1)개 존재할 수 있다. 이 중 N-1개를 골라 MST를 만들었을 때의 최소 비용이 답이다. 2. 대표적인 MST 알고리즘에는 Prim과 Kruscal이 있다. 이 문.. 2022. 1. 12. 이전 1 다음
