kruskal3 SWEA 1251 : 하나로[D4] (c++)_(priority_queue) * 문제 링크 : https://swexpertacademy.com/main/main.do -> 로그인 -> 문제은행 -> '1251' or '하나로' 검색 ** 문제 풀이 방법 Goal) N개의 섬 최소 길이로 모두 연결 - 1 2022. 2. 23. 그래프 알고리즘 Graph algorithm • 최소신장트리(Minimum Spanning Tree) - 프림(Prim) : 한 정점에서 연결된 간선들 중 최단거리를 선택해서 최소신장트리 구성 - 크루스칼(Kruskal) : 최소 가중치 간선을 하나씩 선택해서 최소신장트리를 구성(사이클이 없어야 함) * 간선(edge)의 개수가 적은 경우에는 크루스칼, 간선의 개수가 많은 경우에는 프림 사용이 유리 • 최단경로 • 단일 시작점 최단 경로 문제 - 다익스트라(Dijkstra) : 음의 가중치를 허용하지 X - 벨만-포드(Bellman-Ford) : 음의 가중치 허용하지만 가중치의 합이 음인 사이클은 허용하지 X • 모든 쌍 최단 경로 문제 - 플로이드-워샬(Floyd-Warshall) 1. 최소 신장 트리(MST : Mi.. 2022. 2. 22. SWEA 1251 : 하나로[D4] (c++) * 문제 링크 : https://swexpertacademy.com/main/main.do -> 로그인 -> 문제은행 -> '1251' or '하나로' 검색 ** 문제 풀이 방법 Goal) N개의 섬 최소 길이로 모두 연결 - 1 2022. 2. 13. 이전 1 다음