Problem
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
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 알고리즘을 사용하여 문제를 해결할 수 있었다.
Check out this code in Victoria’s Gist. Please Comment my code in this link.