반응형 개념공부/자료구조2 [Kruskal Algorithm] 크루스칼 알고리즘(feat. Union-find) 크루스칼 알고리즘을 이해하기 위해서는 신장트리, 최소 신장트리에 대한 개념을 먼저 이해해야 한다. 신장트리란 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. * 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다. 이렇게 서로 사이클이 발생하지 않고 모든 정점을 잇는 경로를 신장트리라고 한다. 그럼 최소신장트리(MST)란 무엇일까? 최소 신장 트리(MST)란 최소한의 비용으로 구성되는 신장 트리를 말한다. 이처럼 간선에 대한 가중치가 주어졌을 때 최소한의 가중치를 가지고 모든 정점을 잇는 트리이다. 이제 크루스칼 알고리즘에 대해 알아보겠다 크루스칼 알고리즘이란 MST를 구하는 방식 중 하나로 간선의 가중치의 합이 최솟값이 되도록.. 2021. 9. 16. [Union Find, Disjoint Set] 유니온 파인드 함수 구현 방법(재귀 사용!) 백준 1717번 문제를 풀 때 UnionFind를 사용하였다. 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net Union Find는 그래프알고리즘의 일종으로 여러노드가 존재할 때 각 노드가 연결되어 있는지를 집합을 이용하여 확인하는 방식이다. Union Find를 하기위해서는 크게 3가지의 함수가 필요하다. (꼭 필요한 함수는 2가지 이다) 1. make()함수 - 먼저 각 노드들의 부모노드를 저장할 parents배열을 초기화 시켜준다. (parents 배열을 만드는 .. 2021. 9. 12. 이전 1 다음
