MST (2) 썸네일형 리스트형 Baekjoon 백준 1922 네트워크 연결 문제풀이 kim_ghgh_ 2023. 7. 14. 22:45 📝 1922 문제 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.) 그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. .. 알고리즘 - 최소 신장 트리(Minimum Spanning Tree), 크루스칼(Kruskal), 프림(Prim) Python 코드 최소 신장 트리 (MST) MST : Minimum Spanning Tree 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것 신장 트리 (Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 그래프의 최소 연결 부분 그래프 이다. 최소 연결이란, 간선의 수가 가장 적은 것이다. Spanning Tree의 특징 - DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다 - 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. - Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. MST (Minimum Spanning Tree) 그래프에서 모든 정점을 연결하되, 사이클이 존재하지 않고 간선의.. 이전 1 다음
