[백준/BOJ] 4386번: 별자리 만들기 ( Prim 알고리즘 ) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/4386

 

풀이

이 문제는 주어진 별들을 모두 지나는 트리의 최소 거리의 합을 출력하는 문제입니다.

 

다른 말로 하자면, 별들 간의 거리를 최소로 하는 최소 신장 트리를 구하고, 그 신장 트리의 거리의 합을 출력하는 문제라고 할 수 있습니다.

 

최소 신장 트리를 구하는 알고리즘은 Kruskal과 Prim 알고리즘이 있습니다.

이 글에선 Prim 알고리즘을 사용했습니다.

 

Kruskal 알고리즘은 다른 문제 풀이에서 볼 수 있습니다.

[백준/BOJ] 1197번: 최소 스패닝 트리( Minimal Spanning Tree ) - C++ 문제 풀이

 

Kruskal 알고리즘이 간선의 가중치를 기준으로 최소 신장 트리를 구하는 알고리즘이라면,

Prim 알고리즘은 임의의 정점으로부터 시작해서, 그 정점에 연결된, 가장 작은 가중치를 가진 다른 정점을 선택해 나가면서 최소 신장 트리를 구하는 알고리즘이라고 할 수 있습니다.

 

프림( Prim ) 알고리즘은 여기에 정리해 두었습니다.

[C++] Prim 알고리즘 ( 최소 신장 트리, MST 알고리즘 )

 

아래의 코드를 보기 전에 둘러보면, 나머지를 이해하는데 도움이 될 것입니다.

 

이 알고리즘에선 정점으로부터 최소 거리를 가진 정점을 찾기 위해 우선순위 큐( priority queue )를 사용합니다.

우선순위 큐는 기본값으로 오름차순 정렬을 합니다.

오름차순 정렬을 하면, 최대 값을 가진 원소가 top 위치에 놓이게 됩니다.

 

따라서, 여기에선 사용자 함수 객체를 사용해서 내림차순 정렬을 했습니다.

typedef double MREAL;
typedef pair<int, MREAL> ID_DIST;	// 정점과 정점까지의 거리

// 함수 객체
struct Compare{
    bool operator()( const ID_DIST& d1, const ID_DIST& d2) const{   // 내림차순 (최소 힙)
        return d1.second > d2.second;
    }
};

// 내림차순(최소 힙) 정렬을 하기 위해서 함수 객체를 사용
priority_queue< ID_DIST, vector<ID_DIST>, Compare> pq;

이제, 트리의 루트( root )에 최소 거리를 가진 원소가 위치합니다.

 

우선순위 큐를 사용하는 방법은 여기에서 볼 수 있습니다.

[C++] 우선 순위 큐 ( Priority Queue ) 사용법

 

프림( Prim ) 알고리즘을 적용한 코드는 다음과 같습니다.

typedef double MREAL;
typedef pair<MREAL,MREAL> COORD;
typedef pair<int, MREAL> ID_DIST;

#define SIZE    100	// 정점의 개수
COORD coords[SIZE];	// 정점의 좌표
bool visited[SIZE];	// 정점을 방문했는지 표시

// 정점간의 거리( 가중치 ) 계산
inline MREAL ComputeDist( const COORD& c1, const COORD& c2){
    return sqrt(pow( c1.first - c2.first, 2) + pow( c1.second - c2.second, 2));
}

struct Compare{
    bool operator()( const ID_DIST& d1, const ID_DIST& d2) const{   // 내림차순 (최소 힙)
        return d1.second > d2.second;
    }
};

int main(){

    int n;
    scanf("%d", &n);	정점의 개수

    MREAL x,y;
    for( int i = 0; i < n; i++){

        scanf("%lf %lf", &x, &y);	// 좌표 입력
        coords[i].first = x;
        coords[i].second = y;
    }

    priority_queue< ID_DIST, vector<ID_DIST>, Compare> pq;  // 최소 힙

    MREAL fMinDist = 0;
    pq.emplace(0, 0.0); // 0번 정점으로부터 시작
    
    while( !pq.empty()){

        ID_DIST id = pq.top();	// 가장 거리가 작은 정점 선택
        pq.pop();
        
        int vert = id.first;

        if ( !visited[vert]){	// 아직 도달하지 않은 정점만 순환
        
            fMinDist += id.second;
            visited[vert] = true;

            for( int i = 0; i < n; i++){
                if ( !visited[i]){
                    MREAL dist = ComputeDist( coords[vert], coords[i]);
                    
                    pq.emplace(i, dist); // 정점과 연결된 정점을 입력하고 정렬
                }
            }
        }
    }

    printf("%.2lf", fMinDist);	// 최소 신장 트리의 가중치 합 출력

    return 0;
}

주어진 정점( 여기에선 0번 정점 )으로부터 시작해서, 그 정점과 거리가 가장 가까운 정점을 찾습니다.

이 과정을 위해, 우선순위 큐를 사용합니다.

우선순위 큐에 정점을 넣으면, 가장 가까운 거리를 가진 정점이 자동으로 최상위에 위치합니다. 

이 최상위 정점에서 다시 가장 가까운 정점을 찾아가는 방식입니다.

 

이 과정은 우선순위 큐에 있는 원소의 개수가 0이 되면 종료됩니다.

종료될 때까지, 최소 신장 트리에 포함된 간선의 거리을 합했다가 마지막에 출력하면 끝.

 

소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;

#define SIZE    100

typedef double MREAL;
typedef pair<MREAL,MREAL> COORD;
typedef pair<int, MREAL> ID_DIST;

COORD coords[SIZE];
bool visited[SIZE];

inline MREAL ComputeDist( const COORD& c1, const COORD& c2){
    return sqrt(pow( c1.first - c2.first, 2) + pow( c1.second - c2.second, 2));
}

struct Compare{
    bool operator()( const ID_DIST& d1, const ID_DIST& d2) const{   // 내림차순 (최소 힙)
        return d1.second > d2.second;
    }
};

int main(){

    int n;
    scanf("%d", &n);

    MREAL x,y;

    for( int i = 0; i < n; i++){

        scanf("%lf %lf", &x, &y);
        coords[i].first = x;
        coords[i].second = y;
    }

    priority_queue< ID_DIST, vector<ID_DIST>, Compare> pq;  // 최소 힙

    MREAL fMinDist = 0;
    int vert = 0;   
    pq.emplace(0, 0.0); // start vertex
    
    while( !pq.empty()){

        ID_DIST id = pq.top();
        pq.pop();
        
        vert = id.first;

        if ( !visited[vert]){
        
            fMinDist += id.second;
            visited[vert] = true;

            for( int i = 0; i < n; i++){
                if ( !visited[i]){
                    MREAL dist = ComputeDist( coords[vert], coords[i]);
                    pq.emplace(i, dist);
                }
            }
        }
    }

    printf("%.2lf", fMinDist);

    return 0;
}