[BaekJoon 1197번] 최소 스패닝 트리(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

1197번: 최소 스패닝 트리

 

 

[문제 설명]

 

 

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

 

 

[입력]

 

 

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

 

 

[출력]

 

 

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

 

 

[입출력 예]

 

 

입력	출력
3 3 1 2 1 2 3 2 1 3 3	3

 

 

[문제 풀이]

 

 

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리

↪ 크루스칼 알고리즘을 필요로 하는 문제

 

아래 포스트를 참고해주세요

[Algorithm] 크루스칼(Kruskal)

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;
vector<int> parent;

class Edge {
    public:
        int node[2];
        int cost;
        Edge(int node1, int node2, int cost) {
            this->node[0] = node1;
            this->node[1] = node2;
            this->cost = cost;
        }

        // 비용 오름 차순 정렬을 위해서 필수
        bool operator <(Edge& edge) {
            return this->cost < edge.cost;
        }
};

int getParent(vector<int>& parent,int n1) {
    if(parent[n1] == n1) return n1;
    else return parent[n1] = getParent(parent, parent[n1]);
}

void unionParent(vector<int>& parent, int n1, int n2) {
    n1 = getParent(parent, n1);
    n2 = getParent(parent, n2);

    if(n1 == n2) return;

    if(n1 < n2) parent[n2] = n1;
    else parent[n1] = n2;
}

bool findParent(vector<int>& parent, int n1, int n2) {
    n1 = getParent(parent, n1);
    n2 = getParent(parent, n2);
    if(n1 == n2) return true;
    else return false;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int V, E; cin >> V >> E;
    vector<Edge> v;
    for(int i = 0; i < E; ++i) {
        int n1, n2, cost; cin >> n1 >> n2 >> cost;
        v.emplace_back(Edge(n1, n2, cost)); // 간선 정보 저장
    }
    sort(v.begin(), v.end());
    parent.resize(V + 1, 0);
    for(int i = 1; i <= V; ++i) {
        parent[i] = i;
    }

    int gSize = v.size();
    int gSum = 0;
    for(int i = 0; i < gSize; ++i) {
        if(findParent(parent, v[i].node[0], v[i].node[1]) == false) {
            gSum += v[i].cost;
            unionParent(parent, v[i].node[0], v[i].node[1]);
        }
    }
    cout << gSum;
    return 0;
}