문제 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 최소 스패닝 트리를 구하는 문제로 프림과 크루스칼 알고리즘을 이용해 풀이할 수 있다. 이번 문제에서는 프림 알고리즘을 사용하였다. 프림 알고리즘의 주요 단계는 다음과 같다. 1. 노드 선택: 임의의 노드를 선택하여 시작한다. 2. 우선 순위 큐 생성: 선택한 노드와 연결된 모든 간선을 우선 순위 큐에 추가한다. 이때, 간선의 가중치를 기준으로 오름 차순 정렬된다. 3. 최소 간선 선택: 우선 순위 큐에서 ..

문제 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 이 문제는 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 것으로 크루스칼 알고리즘을 사용한다. 신장 트리란 주어진 그래프에서 일부 간선을 선택하여 모든 노드를 연결하되 싸이클이 없는 트리이다. 여러 신장 트리들 중에서 간선의 가중치의 합이 최소인 것이 최소 신장 트리이다. 최소 신장 트리를 구하는 방법인 크루스칼 알고리즘은 최소 비용으로 모든 노드를 연결하기 위해 사용한다. 먼저 입력받은 그래프를 간선의 가중치를 기준으로 오름차순 정렬한다. 그 후, 가중치가 가장 낮은 간선부터 선택하여 유니온 파인드(Union-..