반응형 프림알고리즘2 프림 알고리즘 프림 알고리즘은 그래프에서 최소 스패닝 트리(Minimum Spanning Tree, MST)를 구하는 알고리즘 중 하나이다. MST란 원래 그래프의 모든 정점을 포함하면서 사이클이 없는 트리다. 최소 스패닝 트리는 그래프의 모든 정점을 가장 적은 비용으로 연결하는 트리를 말한다. 프림 알고리즘의 동작 방식은 1. 임의의 정점을 선택하여 시작 2. 이 정점은 초기에 최소 스패닝 트리에 포함 3. 선택한 정점과 연결된 간선들 중에서 가장 가중치가 작은 간선을 선택 4. 이 간선으로 연결된 정점을 MST에 추가 5. MST에 포함된 정점들과 연결된 간선들 중에서 가장 가중치가 작은 간선을 선택 모든 정점을 MST에 포함시킵니다. 프림 알고리즘은 우선순위 큐 를 사용하여 간선들을 관리하면 효율적으로 구현할 수.. 2023. 7. 26. (Python/🥇3)백준알고리즘 13418번: 학교 탐방하기 문제 바로가기 문제: 국민대학교 홍보대사 국희는 여름방학을 맞아 고등학생들을 대상으로 학교 내부에 있는 건물을 소개해주는 일을 하게 되어 학교 건물을 차례로 소개할 수 있는 이동 경로를 짜보기로 하였다. 국민대학교는 북한산의 정기를 받는 위치에 있어 건물 간 연결된 길이 험난한 오르막길일 수도 있고, 내리막길일 수도 있다. 국희는 먼저 입구를 기준으로 건물 간 연결된 도로가 오르막길인지, 내리막길인지를 파악하여 오르막길인 경우 점선, 내리막길인 경우 실선으로 표시하였다. 건물을 구분하기 쉽도록 번호를 붙였고, 입구에는 숫자 0을 붙이기로 하였다. 그 다음 모든 건물을 방문하는 데 필요한 최소한의 길을 선택하여, 해당 길을 통해서만 건물들을 소개하기로 하였다. 이 과정은 굉장히 신중해야 하는데, 오르막길이.. 2023. 7. 25. 이전 1 다음 반응형
