Beakjoon] 최소 스패닝 트리 (백준 1197 코테) - 그래프 (C++) (최소 신장 트리)

---

🅰️문제주소 : https://www.acmicpc.net/problem/1197

 

🚩문제 

 

 

🪡풀이 

 - 최소 스패닝 트리로 풀으라고 대놓고 준 문제
 - 에지리스트를 구성할때 우선순위 큐를 사용하되 가중치 값으로 정렬 될 수 있도록 연산자 오버로딩을 해줘야한다 
 - find, union을 사용하여 사이클이 만들어지지 않으며 이어질 수 있도록 한다

 

 

☕코드는 아래 숨김

// no64.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct edgeinfo {
    int start;
    int end;
    int64_t w;
    bool operator > (const edgeinfo& edge) const
    {
        return w > edge.w;
    };

};
static vector<int> parent;
static priority_queue<edgeinfo, vector<edgeinfo>, greater<edgeinfo>> edges;
int findP(int a);
void unionfun(int a, int b);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int V, E;
    int64_t result = 0;

    cin >> V >> E;
    parent.resize(V+1);    

    for (int i = 1; i <= V; ++i)
    {
        parent[i] = i;
    }

    for (int i = 0; i < E; ++i)
    {
        int s, e, w;
        cin >> s >> e >> w;
        edgeinfo temp;
        temp.start = s;
        temp.end = e;
        temp.w = w;

        edges.push(temp);
    }

    int edgeCnt = 0;
    while (edgeCnt != V - 1)
    {
        edgeinfo tempEdge;
        tempEdge = edges.top();
        edges.pop();
        if (findP(tempEdge.start) != findP(tempEdge.end))
        {
            unionfun(tempEdge.start, tempEdge.end);
            result += tempEdge.w;
            edgeCnt++;
        }
    }

    cout << result;
    return 0;
}

void unionfun(int a, int b)
{
    int pa = parent[a];
    int pb = parent[b];

    if( pa != pb)
        parent[pb] = pa;
}

int findP(int a)
{
    if (a == parent[a])
        return a;
    else
    {
        return parent[a] = findP(parent[a]);
    }    
}

 

💡알게 된 것 

 - 최소 신장 트리(최소 스패닝 트리) 구하는법
 - union, find 리마인드 함... 이름이랑 대충 역할만 기억나고 구현은 완전 까먹었었다...
 - 구조체 내에서 연산자 오버로딩으로 정렬시킬 수 있는법 리마인드..

---