크루스칼알고리즘 (3) 썸네일형 리스트형 [크루스칼] 난이도2, University of Ulm Local Contest '어두운 길' (Python) 한 마을은 N개의 집과 M개의 도로로 구성되어 있습니다. 각 집은 0번부터 N-1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다. 정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하세요... [크루스칼] 백준 1647번 '도시 분할 계획' (Python) https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 1. 모든 노드를 포함하면서 사이클이 존재하지 않고, 최소비용으로 신장트리를 만들어야 하므로 크루스칼 알고리즘 적용 2. 비용순으로 간선 정렬 3. 사이클이 발생하지 않는 경우에만 집합 합치기 4. 최소 신장트리를 구성하는 간선 중에서 가장 비용이 큰 간선 제거 def find_parent(parent, x): if parent[x]!=x: parent[x] .. [알고리즘] 그래프 - (서로소 집합 / 최소 신장 트리 / 위상 정렬) 트리 자료구조는 최소 힙으로 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조이다. @ 서로소 집합 서로소 집합이란? 공통 원소가 없는 두 집합 서로소 집합 자료구조(union-find 자료구조)란? 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 union : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 find : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 [트리를 이용해 서로소 집합을 계산하는 알고리즘] union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. A와 B의 루트 노드 A', B'를 각각 찾는다. 보통 작은 번호가 부모, 큰 번호가 자식이 된다. A'를 B'의 부모 노드로 설정한다.(B'가 A'를 가리키도록 한다.) 모든.. 이전 1 다음