[Baekjoon,1774]우주신과의 교감

해결

이 문제는 algospot 사이트의 LAN이라는 문제와 해결방법 이 유사하다.
크루스칼의 알고리즘과 프림의 알고리즘 중 나는 프림의 알고리즘으로 해결했다.

프림의 알고리즘은 전체 그래프에서 어느 정점을 시작으로 연결된 간선 중 가장 가중치가 작은 간선을 하나씩 선택해 나아가 최소 스패닝 트리를 만드는 알고리즘이다. 이 문제에서 이미 연결되어 있는 정점들의 간선의 가중치를 0으로 설정하여 해결했다. 이러면 따로 구하지 않아도 되어 편하다.

연결되지 않은 정점은 초기에 INF로 설정하고 갱신해야 하는 시점에 두 점사이의 거리를 구해 간선의 가중치를 형성했다. 선택된 간선들의 가중치의 합을 구하면 결과가 된다.

#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
using namespace std;

const int MAX_V=1001;
const double INF=numeric_limits<double>::max( );

int V,E;
int X[MAX_V], Y[MAX_V];
double adj[MAX_V][MAX_V];

double calcDist(int u, int v)
{
    return adj[u][v]=adj[v][u]=sqrt(pow(X[u]-X[v],2)+pow(Y[u]-Y[v],2));
}

double prim()
{
    vector<double> minDist(V,INF);
    vector<bool> added(V,false);
    
    double ret=0.0;
    minDist[0]=0;
    for(int it=0;it<V;++it)
    {
        int u=-1;
        for(int v=0;v<V;++v)
            if(!added[v] && (u==-1 || minDist[u]>minDist[v]))
            {
                u=v;
                if(minDist[u]==0)
                    break;
            }
        
        added[u]=true;
        ret+=minDist[u];
        for(int v=0;v<V;++v)
        {
            if(added[v])
                continue;
            double dist=(adj[u][v]==INF) ? calcDist(u,v) : adj[u][v];
            minDist[v]=min(minDist[v],dist);
        }
    }
    return ret;
}

int main()
{
    cin>>V>>E;
    
    for(int i=0;i<V;++i)
        cin>>X[i]>>Y[i];
    
    for(int i=0;i<V;++i)
        for(int j=0;j<V;++j)
            adj[i][j]=INF;
    
    for(int i=0;i<E;++i)
    {
        int a,b;
        cin>>a>>b;
        --a; --b;
        adj[a][b]=adj[b][a]=0;
    }
    cout<<fixed;
    cout.precision(2);
    cout<<prim()<<endl;

    return 0;
}

회고

초기에 minDist를 minDistSqr 형태로 저장했는데 이는 위치가 1,000,000이 될 수 있기 때문에 int형 자료형은 초과될 수 있다. 이 때문에 한참 디버깅했다. 결국 double로 선언하여 sqrt()를 적용한 상태로 저장하니 쉽게 해결되었다.