프림 알고리즘3

• [백준/BOJ] 14950번: 정복자 문제 https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 해설 모든 도시를 정복하는데 드는 최소 비용을 구하는 문제이다. 이 문장을 보고 MST 알고리즘을 떠올려야 한다. MST를 떠올렸다면, 이를 크루스칼 알고리즘과 프림 알고리즘 중 어떤 알고리즘으로 해결할지 정해야 한다. 이 문제는 1번 도시부터 시작해서 이와 연결된 도시를 정복해나가야 한다. 따라서 프림 알고리즘이 더 적절하다 생각했다. 문제를 보면 "한 번 도시가 정복되면, 모든 도시는 경계를.. PS(Problem Solving)/BOJ 2022. 7. 28.

• [백준/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.