[백준] 1197번_최소 스패닝 트리 C++

27 Mar 2023 in Study on Coding Test

프림 알고리즘과 크루스칼 알고리즘을 사용해서 풀 수 있다.

나는 프림 알고리즘을 사용하였다.

정답제출코드

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

using namespace std;

int V, E, MSTWeight = 0;

struct Edge
{
    int start, end;
    int weight;

    Edge(int _start, int _end, int _weight):
    start(_start),
    end(_end),
    weight(_weight)
    {}

    bool operator < (const Edge _other) const
    {
        if (weight >= _other.weight)
            return true;
        else
            return false;
    };
};

bool visited[10001] = {false};
vector<Edge> EdgeList[10001];

void prim()
{
    priority_queue<Edge> pq;

    Edge StartEdge(1, 1, 0);
    pq.push(StartEdge);

    while (!pq.empty())
    {
        Edge cur = pq.top();
        pq.pop();
        
        if (!visited[cur.end])
        {
            visited[cur.end] = true;
            MSTWeight += cur.weight;

            for (size_t i = 0; i < EdgeList[cur.end].size(); ++i)
            {
                if (!visited[EdgeList[cur.end][i].end])
                    pq.push(EdgeList[cur.end][i]);
            }

        }
    }
    
}

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

    cin >> V >> E;

    for (int i = 0; i < E; ++i)
    {
        int A, B, C;
        cin >> A >> B >> C;

        Edge e1(A, B, C);
        Edge e2(B, A, C);

        EdgeList[A].push_back(e1);
        EdgeList[B].push_back(e2);
    }

    prim();

    cout << MSTWeight;

    return 0;
}

Edge 구조체를 정의해서 풀었다.

우선순위큐는 가중치가 작은 Edge가 우선순위가 높도록 구현하였다.

Edge StartEdge(1, 1, 0);

이 코드는 1번 정점부터 시작할 수 있도록 임시 간선을 설치한 것이다.

그러고나서 1번 정점과 연결된 간선을 가중치가 작은 것부터 탐색하도록 구현하였다.

그리고 간선을 통해서 가는 다음 노드가 미방문 상태일 경우에만

간선이 우선순위 큐에 추가되도록 구현하였다.

리스트가 아니라 구조체로 풀다보니 약간 헷갈렸다.