글 읽기 - 최소신장트리문제 질문입니다 도움이 필요함미다ㅠ

sontg123 3년 전 0

일단 코드는 프림+ unionfind 사용해서 풀어본 코드입니다

랜덤 start(일단은1)부터 각 정점에서의 거리가 최소값인 것을 pq로 찾아서 풀었는데 생각해보니 연결이 따로따로 되있을때 연결 후에 그 연결된 다른 점들에서의 거리를 체크하지 못하더군요

크루스칼로 풀자니 n이 1000인데 그럼 연결성분이 1000*(1000+1)/2 개가 나올테고 이거 거리들을 다 계산해서 정렬할라면 정렬만 5억이 넘어가는데 이게 시간이 될까 싶어서 일단 버렸습니다 (연결 되있는거 제외한다 쳐도 연결 안되있을테도 풀려야 할테니까..)

아이디어가 궁굼합니다 ㅜㅜ 힌트라도 주시면 감사하겠습니다

----------------------------------------------------------------------------------------------------

혹시나 같은 고민을 하는 분들을 위해 남깁니다

prim으로 풀때 이미연결된 점들 사이의 거리를 0으로 해서 기본과 같이 돌리면 통과가 됩니다

그리고 좌표 범위가1,000,000이라 double형 사용하면 됩니다!

코드는 고민하던 통과x인 코드 그대로 남겨두겠습니다~

#include <iostream>
#include <vector>
#include <math.h>
#include <queue>
using namespace std;
struct _node{
    int parent;
    int x,y;
};
struct compare{// pq정렬을 위한 pair 연산자 객체
    bool operator()(pair<int,float>& a,pair<int,float>& b){
        return a.second>b.second;
    }

};
class unionfind_prim{
private:
    vector<_node> node;
    int N,M;
public:
    unionfind_prim(){
        std::cin >> N >> M;
        node.resize(N+1,{-1,});
        set_val();
    }
    int find(int n){
        if(node[n].parent<0)
            return n;
        return node[n].parent = find(node[n].parent);
    }
    bool merge(int a,int b){
        int p_a=find(a);
        int p_b=find(b);
        if(p_a==p_b)
            return false;
        node[p_b].parent=p_a;
        return true;
    }
    void set_val(){//x y 받아서 저장하고 m개 받아서 연결시킴
        for(int i=1;i<=N;i++)
            std::cin >> node[i].x >> node[i].y;
        int a,b;
        for(int i=0;i<M;i++){
            std::cin >> a >> b;
            merge(a,b);
        }
    }
    float distance(_node& a,_node& b){//거리계산함수
        float dx= a.x-b.x;
        float dy=a.y-b.y;
        return sqrt(dx*dx+dy*dy);
    }


    void prim(){
        int start=1;
        priority_queue<pair<int,float>,vector<pair<int,float>>,compare> pq;//정점과 거리들을 pq에저장
        pq.push({start,0});
        int cur;
        float c_dis,sol=0,tmp;
        while(!pq.empty()){
            cur =pq.top().first;
            c_dis = pq.top().second;
            std::cout << cur <<"!!\n";
            pq.pop();
            
            if(!merge(0,cur)) //merge가 안되면 이미 연결되있는 거니 체크안함
                continue;
            sol+=c_dis;
            for(int i=1;i<=N;i++){//1부터 N까지 같은 조상을 갖지 않는 정점들 pq에 저장
                if(find(cur)!=find(i)){
                    tmp=distance(node[cur],node[i]);
                    pq.push({i,tmp});
                    std::cout << i <<','<<tmp<< ' ';
                }
            }
            std::cout << '\n';
        }
        printf("%.2f",sol);
    }
};
int main(){
    unionfind_prim unifr;
    unifr.prim();

    return 0;    
}

Green55 3년 전 1

5억이란 값이 어떻게 나오신지 모르겠는데, 1000^2 * log2(1000^2)은 그렇게 큰 값이 아닙니다. 충분히 정렬 됩니다.

댓글을 작성하려면 로그인해야 합니다.