Prim Algorithm2

• [백준/BOJ] 13418번: 학교 탐방하기 문제 https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 해설 MST는 최소 신장 트리이다. 즉, 가중치가 가장 낮은 트리를 구하는 것이다. 이는 크루스칼 알고리즘과 프림 알고리즘으로 구할 수 있다. 그렇다면 반대로 신장 트리 중 최악의 경우도, 크루스칼 알고리즘과 프림 알고리즘으로 구할 수 있다는 얘기가 된다. 이 문제에서는 (최악일 경우의 피로도 - 최소일 경우의 피로도)를 구해야 한다. 나는 입구에서 시작을.. PS(Problem Solving)/BOJ 2022. 7. 26.

• 

  [알고리즘] 프림 알고리즘(Prim Algorithm) 프림 알고리즘 무방향 연결 그래프가 주어졌을 때, 최소 신장 트리를 찾기 위한 알고리즘이다. 크루스칼 알고리즘과의 목적은 같지만, 언제 어떻게 사용하느냐에 따라 효율성이 달라질 수 있다. 크루스칼 알고리즘에 관해서는 크루스칼 알고리즘을 참고하면 된다. 크루스칼 알고리즘과 마찬가지로 프림 알고리즘도 그리디 알고리즘(Greedy Algorithm)의 일종이다. 크루스칼 알고리즘은 간선의 가중치를 오름차순으로 정렬해서 가장 작은 가중치를 가진 간선부터 선택해나갔다. 프림 알고리즘은 임의의 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장시키는 기법이다. 프림 알고리즘의 동작 위에서도 말했듯이, 프림 알고리즘은 그리디 알고리즘의 일종이다.' 즉, 탐색 정점과 연결된 인접 정접들 중 가중치가 가장 적은 간선.. Algorithm 2022. 7. 24.