728x90 반응형 크루스칼2 백준 1922번: 네트워크 연결 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.) 그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용.. 2022. 8. 11. 8. 기타 그래프 이론: 크루스칼 알고리즘 크루스칼 알고리즘 최소 신장 트리를 찾는 알고리즘 최소 신장 트리는 사이클이 존재하지 않고 모든 노드가 연결되어 있어야 함 모든 도시가 연결되어야 하고 도로 건설 비용을 최소화 해야할 때 크루스칼 알고리즘을 사용하면.. 도로를 짓는 데 필요한 최소 비용을 계산할 수 있다 먼저 간선의 정보를 입력받는다(노드1,노드2,비용) 비용에 대하여 오름차순으로 정렬한다 비용이 적게 드는 순으로 노드1,노드2가 사이클이 아니라면(부모 노드가 같지 않다면) 노드 1,2를 union연산을 수행하고, 노드1,2의 부모노드가 같다면 무시한다 동그라미 안 숫자는 각 간선의 비용에 대하여 오름차순으로 번호를 매긴 것이고, 그래프에서 빨간 선은 연결된 것, 파란 선은 연결하지 않고 무시한 것이다 def find_parent(par.. 2022. 8. 8. 이전 1 다음 728x90 반응형
