최소비용신장트리2 [C++] 백준 1922번: 네트워크 연결 (최소 비용 신장 트리) https://www.acmicpc.net/problem/1922문제 이해하기 문제의 요구사항은 다음과 같습니다.모든 컴퓨터를 연결하는 데 필요한 최소 비용을 구하여라. 모든 컴퓨터를 연결하는 데 최소 비용으로 연결해야 합니다. 다시 말해, 모든 노드를 연결하는 데 최소 비용으로 연결해야 합니다. 즉, 최소 신장 트리(Minimum Spanning Tree)의 비용을 구하는 문제입니다.시간복잡도 어림하기크루스칼(Kruskal) 알고리즘, 프림(Prim) 알고리즘 최소 비용 신장 트리를 구하기 위해 일반적으로 크루스칼 알고리즘과 프림 알고리즘을 사용합니다. 두 알고리즘의 차이는 구현 방식에 있습니다. 크루스칼 알고리즘은 사이클을 형성하지 않는 간선을 선택하며 최소 비용 신장 트리를 찾고, 프림 알고리즘은.. 2024. 6. 20. [C++] 백준 1197번 최소 스패닝 트리 (최소 비용 신장 트리) https://www.acmicpc.net/problem/1197문제 이해하기 문제의 요구사항은 다음과 같습니다.그래프가 주어졌을 때, 최소 스패닝 트리의 가중치를 구하여라. 최소 스패닝 트리(MST, Minimum Spanning Tree)란 모든 노드가 사이클이 없이 연결되어 있을 때, 가장 작은 가중치를 가지는 것을 말합니다. 이를 구하는 알고리즘으로는 크게 Prim 알고리즘과 Kruskal 알고리즘 두 가지가 있습니다. 시간복잡도 어림하기Prim 알고리즘 Prim 알고리즘은 정점 선택 기반으로 최소 신장 트리를 구성합니다. 과정은 다음과 같습니다.1. 시작 정점을 MST 집합에 포함한다.2. MST 집합에 포함된 노드와 인접한 노드들 중 가장 작은 가중치를 가지는 노드를 선택하고, MST 집합에.. 2024. 6. 4. 이전 1 다음