크루스칼
[C++] 개인적인 (MST 알고리즘) 크루스칼 & 프림 구현
사용할 데이터는 다음과 같다. 결과) 17 1 2 2 2 6 7 3 2 3 3 6 8 4 3 5 4 2 3 4 1 1 5 1 4 5 4 9 공통으로 쓰여짐 // 간선 개수 const int edge = 9; struct sNode { public: int from = 0, to = 0, weight = 0; /*sNode() = default; sNode(int from, int to, int weight) : from(from), to(to), weight(weight) { }*/ bool operator(const sNode& ref) const { return weight > ref.weight; } bool operator==(const sNode& ref) const { return from =..
[골4] 1647 - 도시 분할 계획
#include #include #include #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ using namespace std; using IntPair = pair; using NodePair = pair; vector graph; int parent[100001]; int Find(int x) { if (parent[x] == x) return x; else return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a), b = Find(b); parent[a] = b; } bool IsCycle(int a,..
C++ MST 크루스칼 + 프림 알고리즘 코드
이미지 출처) Minimum Spanning Tree - Kruskal - Algorithms for Competitive Programming (cp-algorithms.com) 정답) 1 + 2 + 3 + 4 + 7 = 17 순회하는 순서가 추가되는 노드 순서에 따라 상이할 수 있음. 입력 데이터 From 1 To 2 Value 2 Edge형 구조체에 담음, int from, to, val; 9 1 2 2 1 4 1 1 5 4 2 4 3 2 3 3 2 6 7 3 6 8 4 3 5 5 4 9 0 0 0 크루스칼 알고리즘 핵심 포인트) 모든 부모 노드들을 포함하고 있을 int형 벡터와 Edge형 벡터, 한 방향만 연결. #include #include #include using namespace std;..
[골4] 4386 - 별자리 만들기
#include #include #include #include #pragma region 빠른 입출력 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; using dp = pair; #define MAX 101 #define x first #define y second vector star; vector coord; int parent[MAX]; double ans; int GetParent(int a) { return (parent[a] == a) ? a : parent[a] = GetParent(parent[a]); }..
[골4] 1197 - 최소 스패닝 트리
#include #include #include using namespace std; class Edge { public: int node[2]; int dist; Edge(int a, int b, int dist) { node[0] = a; node[1] = b; this->dist = dist; } bool operator> vertex >> edge; for (int i = 0; i > from >> to >> cost; v.push_back(Edge(from, to, cost)); } sort(v.begin(), v.end..
최소 스패닝 트리 (MST) / 크루스칼 알고리즘 (Kruskal Algorithm)
최소 스패닝 트리 (MST, Minimum Spanning Tree) 그래프의 스패닝 트리(신장 트리, Spanning Tree)란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 의미한다. 위와 같은 그래프에서, 양쪽의 붉은 간선으로 이어진 부분 그래프들은 모두 스패닝 트리에 해당한다. 즉, 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면, 그것이 곧 스패닝 트리이다. 스패닝 트리는 이름처럼 트리의 일종이므로, V개의 모든 정점을 연결하는 간선의 수는 V - 1개이다. 최소 스패닝 트리(MST)는 이러한 스패닝 트리 중, 간선의 가중치 합이 최소가 되는 스패닝 트리를 말한다. 이러한 최소 스패닝 트리를 구하는 알고리즘은 대표적으로 Kruskal, Prim 알고리즘이 존재한다. 크루스..