kruskal(2)
-
[알고리즘] 3124. 최소 스패팅 트리
0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 최소 신장 트리 (MST) Kruskal Prim 2. 제출 MST를 구하는 문제다. 주어지는 가중치가 크기 때문에 overflow를 주의하면서 풀면 된다. 가. Kruskal import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class SWEA3124 { static int V, E; static long ret; // int overflow 발생 sta..
2024.02.26 -
[Java] 최소 신장 트리
1. 최소 신장 트리 (MST) 신장 트리 n개의 정점으로 이루어진 무향 그래프에서 n개 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 (Minimum Spanning Tree) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 알고리즘 방식 시간 복잡도 유리한 상황 자료구조 Kruskal 일반적 O(ElogE + V) 간선이 많지 않은 그래프 간선 리스트 Prim (PQ 구현) 우선순위 큐(PQ) 사용 O(ElogV) 또는 O(ElogE) 간선이 많지 않은 그래프 인접 행렬, 인접 리스트 Prim (반복문 구현) 반복문 사용 O(V^2) 간선이 많은 밀집 그래프 인접 행렬, 인접 리스트 (E : 간선의 수, V : 정점의 수) But! PQ..
2024.02.25