탐욕 알고리즘을 기반으로 당장의 최소 비용을 선택하여 최적의 솔루션을 찾는다.
키 포인트는 사이클이 생기는 여부를 확인하는 것 알고리즘이다.
사이클이 생기는 여부를 확인하는 알고리즘
Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘
노드들 중에 연결된 노드를 찾거나, 노드들을 서로 연결할 때(합칠 때) 사용
Disjoint Set
동작 순서
int getParent(int parent[], int x)
함수를 만든다. 이는 재귀적으로 부모 노드를 확인하기 위한 것으로 부모 노드의 번호가 반환된다.void unionParent(int parent[], int a, int b)
함수를 만든다. 이는 두 노드를 합치는 것으로 노드 번호가 작은 것이 부모 노드가 된다.int findParent(int parent[], int a, int b)
함수를 만든다. 이는 같은 부모 노드를 가지는지 확인하는 함수이며 같은 부모 노드를 가진다면 1을 반환하고 다른 부모 노드를 가진다면 0을 반환한다.#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//부모 노드를 재귀적으로 파악한다.
int getParent(int parent[], int x) {
if (parent[x] == x) return x;
return parent[x] = getParent(parent, parent[x]);
}
//각 부모 노드를 합친다. 이때 작은 값을 부모 노드로 한다.
void unionParent(int parent[], int a, int b) {
a = getParent(parent, a);
b = getParent(parent, b);
if (a < b) parent[b] = a; //작은 값을 부모 노드로
else parent[a] = b;
}
//같은 부모 노드를 가지는지 확인한다.
//같은 부모 노드를 가진다면 이미 연결되어 있다는 것을 의미한다.
int findParent(int parent[], int a, int b) {
a = getParent(parent, a);
b = getParent(parent, b);
if (a == b) return 1; //같은 부모 노드를 가진다면 1 반환
else return 0; //다른 부모 노드를 가진다면 0 반환
}
//Edge class 선언
class Edge {
public:
int node[2]; //0번에는 시작 노드, 1번에는 도착 노드
int distance; //노드 사이의 거리
Edge(int a, int b, int distance) { //객체 생성자
this->node[0] = a;
this->node[1] = b;
this->distance = distance;
}
bool operator <(Edge& edge) { //< 연산자 오버로딩을 하여 distance를 기준으로 비교되도록 한다.
return this->distance < edge.distance;
}
};
int main()
{
vector<Edge> v;
int parent[10001];
int V, E;
cin >> V >> E;
for (int i = 0; i < E; i++) {
int A, B, C;
cin >> A >> B >> C;
v.push_back(Edge(A, B, C));
}
//부모 노드 저장 배열을 모두 자기 자신으로 초기화한다.
for (int i = 1; i <= V; i++) {
parent[i] = i;
}
sort(v.begin(), v.end()); //distance를 기준으로 모든 Edge를 오름차순 정렬한다.
int sum = 0; //최소 거리 저장, 0으로 초기화
for (int i = 0; i < v.size(); i++) { //거리가 작은 Edge부터 시작한다.
if (!findParent(parent, v[i].node[0], v[i].node[1])) { //부모 노드가 다를 경우, 즉 사이클이 생기지 않는 경우
sum += v[i].distance; //거리 누적 합
unionParent(parent, v[i].node[0], v[i].node[1]); //두 노드 합치기 union
}
}
cout << sum << '\n'; //최소 거리 출력
}