목록최소비용신장트리 (1)

algoqna

[BOJ 1922] 네트워크 연결

1. MST라는 개념에 대해 모른다면 최소 비용 신장트리 링크 참조 2. Union-Find에 대해 모른다면 Disjoint-Set 링크 참조 최소 비용 신장트리(MST : Kruskal / Prim) * 최소비용 신장트리: 간선의 가중치가 가장 작은 것부터 처리하여 정점들을 모두 연결, 최소의 비용을 가지는 트리 생성 KRUSKAL 1) 모든 간선을 가중치에 따라 오름차순으로 정렬 ● KRUSKAL 알고리 kkalgo.tistory.com Disjoint-Set (상호 배타적 집합) - 트리 이용 Union-Find 1) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 ● 0 ~ n-1 까지의 원소로 표현한 뒤, 각 1개의 원소를 포함하는 n개의 집합을 만들어야 함 ..
프로그래밍/기타 문제풀이 2023. 5. 7. 19:38
이전 Prev 1 Next 다음