백준 1922번 네트워크 연결

문제 링크입니다: https://www.acmicpc.net/problem/1922

MST(Minimum Spanning Tree) 문제였습니다.

우선순위 큐를 이용하면 쉽게 풀 수 있는 간단한 문제였습니다.

알고리즘은 아래와 같습니다.

1. minHeap을 구성하는 우선순위 큐를 선언합니다.

2. 1번 정점부터 최소 스패닝 트리를 구성하기 시작합니다.

3. 최소힙의 루트에 있는 정점을 확인합니다.

i) 이미 방문한 정점이라면 최소 가중치가 아니기 때문에 패스

ii) 방문하지 않은 정점이라면 가중치를 결과에 더해주고 해당 정점과 연결된 정점들 중 방문하지 않은 정점들을 우선순위 큐에 넣습니다.

4. 3번을 반복하면서 얻은 가중치의 합들을 출력합니다

#include <iostream>

#include <vector>

#include <queue>

#include <functional>

using namespace std;

 

const int MAX = 1000 + 1;

 

int N, M;

vector<pair<int, int>> graph[MAX];

//minHeap

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

bool visited[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N >> M;

 

        for (int i = 0; i < M; i++)

        {

                 int a, b, c;

                 cin >> a >> b >> c;

 

                 //양방향

                 graph[a].push_back({ c, b });

                 graph[b].push_back({ c, a });

        }

 

        //1번 정점부터 시작

        pq.push({ 0, 1 });

        int result = 0;

 

        while (!pq.empty())

        {

                 int cost = pq.top().first;

                 int vertex = pq.top().second;

                 pq.pop();

 

                 if (!visited[vertex])

                 {

                         visited[vertex] = true;

                         result += cost;

 

                         for (int i = 0; i < graph[vertex].size(); i++)

                         {

                                 int nextCost = graph[vertex][i].first;

                                 int nextVertex = graph[vertex][i].second;

 

                                 if (!visited[nextVertex])

                                          pq.push({ nextCost, nextVertex });

                         }

                 }

        }

 

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~