백준, BOJ, 1922번, 네트워크 연결 : C++ [CPP] ★★★★

문제에서

모든 컴퓨터가 연결되었다.

최소비용이다를 보고

최소신장트리가 생각나면 정답이다.

https://www.acmicpc.net/problem/1922

 

---

 

#맞는 풀이

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

#define MAX 1001

using namespace std;
using ti3 = tuple<int,int,int>;

int n,m;

vector<pair<int,int>> adj[MAX]; //1000개는 인접행렬로 부담스러움(뭐 1000개까진 괜찮다 사실)
//cost, to가 들어갈 예정

bool check[MAX]; //이미 이어져있는지 확인


int Prim(){
    int cnt = 0;
    int tot = 0;
    priority_queue<ti3, vector<ti3>, greater<ti3>> heap;
    //1번부터 시작함
    for(auto next : adj[1]){
        //next.first 자신의 코스트
        //next.second는 자신과 이어진 노드
        heap.push({next.first, 1,next.second}); //1번노드부터 시작,(1번노드에 연결된 모든 간선 집어넣음)
    }
    check[1] = 1; //MST만드는데 쓰임
    
    while(1){
        int cost, v1, v2;
        tie(cost,v1,v2) = heap.top(); //v1은 MST를 이루고 있는 노드, v2는 MST가 아닌 노드
        heap.pop();
        if(check[v2]) continue; //만약 포함된 노드라면 다음 노드로.
        
        check[v2] = 1; //MST만드는데 쓰임
        tot += cost; //간선 비용 추가.
        cnt++;
        if(cnt == n-1) break; //MST는 노드 개수 - 1의 간선을 가짐
        //v2에 연결된 간선들 heap에 넣음
        for(auto next : adj[v2]){
            if(!check[next.second]){
                heap.push({next.first, v2, next.second});
            }
        }
    }
    return tot;

}

int main(){
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int from, to, cost;
        cin >> from >> to >> cost;
        adj[from].push_back({cost, to});
        adj[to].push_back({cost, from});//양방향 그래프
    }
    
    int ans = Prim(); //1번부터 시작한 MST
    
    cout << ans;
    
    
}

 

 

Kruskal 풀이와 Prim 풀이가 있지만

Prim이 조금 더 직관적이라서 그냥 Prim으로 풀었다.

 

다익스트라와 같은 점이라면 최소 힙을 이용한다는 것?

그리고 노드가 1000개정도 되면.. 이제 인접행렬을 표현할 때야 괜찮지만

노드가 10000개가 되면 인접행렬로 표현하면 안된다.

그냥 인접행렬만 400메가정도 먹을 것이기 때문이다.

 

그때는 vector로 실제 연결된 것만 파악하도록 하자.