1922_네트워크의 연결

Concept & Idea

당연히 이 문제를 DFS로 풀면 시간초과가 엄청 날 것이다.(1000의 100000승?) 이 문제는 최소 스패닝 트리를 구하는 문제로, Prim 알고리즘을 이용하여 해결할 수 있었다. 우선순위 큐를 문제에서 해결하는 것은 처음이었기 때문에, 다소 생소했으나 대체적으로 큐와 동일하였다.

struct node { int x,y,z; bool operator() (node a, node b) { return a.z>b.z; //최소값 우선 노드 } };

이 노드를 만듬으로써, operator를 통해 comp함수까지 대체할 수 있었다.

priority_queue<node, vector, node> pqu;

이 코드는 priority_queue를 선언하는 코드인데, 첫번째는 queue의 타입, 두번째 변수인 vector는 priority_queue가 벡터처럼 구현되어서 넣는 코드란다.. 컨테이너? 세번째 변수는 comp함수가 들어가는 곳인데, node 구조체 안에 생성한 operator() 함수를 통해서 선언할 수 있었다.

Code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node {
    int x,y,z;
    bool operator() (node a, node b) {
        return a.z>b.z; //최소값 우선 노드
    }
};
vector<pair<int, int>> vec[1001]; //node, cost 순
bool check[1001];
int n,line,res=0;
priority_queue<node, vector<node>, node> pqu;
int main(){
    cin>>n>>line;
    for(int i=0; i<line; i++) {
        int a,b,c;
        cin>>a>>b>>c;
        vec[a].push_back({b,c});
        vec[b].push_back({a,c});
    }
    for(int i=0; i<vec[1].size(); i++) {
        node temp;
        temp.x=1; temp.y=vec[1][i].first; temp.z=vec[1][i].second;
        pqu.push(temp);
    }
    check[1]=true;
    while(!pqu.empty()) {
        node temp = pqu.top();
        pqu.pop();
        if(!check[temp.y]) {
            check[temp.y]=true;
            res+=temp.z;
            for(int i=0; i<vec[temp.y].size(); i++) {
                if(!check[vec[temp.y][i].first]) {
                    node k;
                    k.x=temp.y; k.y=vec[temp.y][i].first; k.z=vec[temp.y][i].second;
                    pqu.push(k);
                }
            }
        }
    }
    cout<<res<<endl;
}

 

Fealing

처음으로 우선 순위 큐를 이용하여, 그 중에서도 Prim 알고리즘을 이용하여 문제를 해결하였다.
처음에 어떻게 해결할까 생각했을 때, DFS가 떠올랐고, 컴퓨터의 수 N이 1000이고 간선의 수가 100000이어서 1000^100000은 무조건 시간초과이기에 바로 접었다.
그러고 생각한 방법이 최솟값만 찾아서 연결하면 되겠다! 였는데, 추가된 노드와 연결된 최소값만 연결한다고 문제가 해결되는 것은 아닌 것 같았다.
So! 내가 현재 연결된 모든 노드와 연결된 간선들 중 최솟값을 추가해나가는 방식으로 문제를 해결할 수 있을 것 같았고, 최소 스패닝 트리를 구하는 Prim 알고리즘을 사용하여 문제를 해결할 수 있었다.