유니온파인드

[c++] 백준 1197 풀이 (MST, 최소 신장 트리, 그래프, 유니온 파인드)

이번에는 MST를 풀어보자. MST는 Minimum Spanning Tree의 약자로 span이란 기간을 의미해서 직역하면 최소화된 기간 트리이다. 좀 더 풀어 말하면 트리가 낮은 가중치로 연결되어 있다고 볼 수 있다. 다르게는 그래프의 최소 연결 부분 그래프 라고 할 수 있다. 이번 문제를 풀기 위해서는 MST를 알기 이전에 Spanning Tree에 대해서 이해해야한다. Spanning Tree 간선 수가 가장 작게 연결된다. 만약 정점이 V개라면 V-1개로 연결된 트리 사이클이 존재하지 않는다.(트리의 형태) Minimum Spanning Tree 값이 가장 작은 간선을 이용하여 만든 Spanning Tree 간선 가중치 합이 최소여야 한다. 사이클이 존재하지 않는다. 크루스칼 알고리즘과 프림알고리..

[c++] 백준 1717 풀이 (집합의 표현, 그래프, 서로소 집합, 유니온파인드)

서로서 집합은 상호 배타적 집합(Disjoint-set) 이라고 한다. 교집합이 공집합인 집합(서로소 집합) 들의 정보를 확인하고 조작할 수 있는 자료구조이다. - union : 두 노드를 한 그래프로 합친다. - find : 어떤 노드가 속한 집합을 반환 이 문제는 유니온 파인드를 이용하여 두 노드가 해당하는 집합을 합치거나 한 노드가 다른 노드의 집합에 속하는지 판별하는 문제이다. 따라서 union함수를 구현하고, find함수를 구현하여 풀이를 진행한다. 우선 find함수를 구현한다. find함수의 역할은 해당 노드의 부모로 탐색을 진행한다. 따라서 루트 노드를 만나는 경우 반환을 진행하며, 루트 노드가 아닌 경우에는 해당 노드의 부모에 루트 노드 값을 입력해준다. (즉 find과정을 통해 tree를..