크루스칼알고리즘2 [백준][트리] 1197 최소 스패닝 트리(크루스칼 알고리즘) 이 문제는 최소 스패닝 트리를 구현하는 방법중 크루스칼 알고리즘을 이용하여 구현하면 된다. 크루스칼 알고리즘은 그래프 사이 연결의 최소비용을 찾으면 된다. 간선을 비용순으로 정렬하고,가장작은 비용이 들어가는 간선을 사이클이 생기지 않는 순서대로 선택하면된다. 간선 사이의 사이클은 union, find 연산을 이용하여 처리한다. https://www.acmicpc.net/problem/1197 2017. 7. 6. [백준] 1717 집합의 표현(유니온 파인드) 유니온 파인드 상호 배타적 집합이라고도 한다. 2가지 연산으로 이루어져 있다. 1. Find: x가 어떤 집합에 포함되어 있는지 찾는 연산2. Union: x와 y가 퐇마되어 있는 집합을 합치는 연산- 구현은 트리를 이용해서 한다. - parent[i] = i 의 parent 가 저장되어 있음 * parent[] 배열을 각자 자기 번호로 초기화 하는 것에 주의** find 연산에서 결과를 가지고 있다가 저장하고 반환하는 것에 주의 *** 이 union, find 연산은 MST의 크루스칼 알고리즘에 사용된다. https://www.acmicpc.net/problem/1717 2017. 7. 6. 이전 1 다음