[Greedy Approach 예제] 백준 1197 (kruskal)

[Greedy Approach 예제] 백준 1197 (kruskal)

문제

문제 풀이

int parent[10001]; struct edge { int u, v, w; edge(int u, int v, int w) { this->u = u; this->v = v; this->w = w; } }; //initial : n개의 부분집합을 초기화하고 하나의 원소들이 들어가잇도록 한다. //find(i) : point 만들기 int find(int u) { if (u == parent[u]) return u; return parent[u] = find(parent[u]); } void merge(int u, int v) { u = find(u); v = find(v); parent[v] = u; } int compare_comp(const edge& a, const edge& b) { return a.w < b.w;//edge값은 세번째 인자이니까. } int main() { cin >> V >> E; vector v; for (int i = 1; i <= V; i++) { parent[i] = i; }//(1) vertex들의 모임, Initial(). 하나의 set에 하나의 원소들어간다. int A, B, C; for (int i = 0; i < E; i++) { cin >> A >> B >> C; v.push_back(edge(A, B, C)); } sort(v.begin(), v.end(), compare_comp);//(2) edge 오름차순 정렬 for (auto vertex : v) { if (find(vertex.v) != find(vertex.u)) {//(3) 같은 set에 있는지 확인한다. merge(vertex.u, vertex.v);//(4) 다른 set인 경우 merge ans += vertex.w;// } } cout << ans; return 0;

find, merge 함수

int find(int u) { if (u == parent[u]) return u; return parent[u] = find(parent[u]); } void merge(int u, int v) { u = find(u); v = find(v); parent[v] = u; }

find() : 해당 원소가 어느 set에 있는지 찾고 set의 부모노드를 반환한다

merge() : 찾은 두개의 원소를 같은 set에 넣어야 한다. 두번째 노드의 부모노드를 첫번째 원소로 대입해 연결시킨다.

from http://bohyeonstudy.tistory.com/122 by ccl(A) rewrite - 2021-08-17 12:00:24