신장트리 (2) 썸네일형 리스트형 [크루스칼] 백준 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 다음