MST 최소신장트리 - 프림 알고리즘

프림 알고리즘또한 MST 를 해결하는 알고리즘이다.

 

이 알고리즘의 특징은 그리디한 방식으로 문제를 접근하며,

프림 알고리즘은 어떠한 자료구조를 사용하는지에 따라 효율성이 달라진다.

 

Priority Queue 를 활용하면 간선의 선택을 효율적으로 할수있고 

이경우 시간복잡도는 O((V+E log V)) 가 된다.

 

① 시작 정점을 기반으로 인접한 정점을 확인한뒤

우선순위 큐에 가중치 기준으로 데이터를 넣어준다.

이때 시작 정점은 방문된 상태라고 표기해준다.

 

② 큐에서 추출된 정점을 방문으로 표기해준뒤

인접한 정점을 확인한뒤 ①의 과정과 마찬가지로 큐에 넣어준다.

 

③ 위 과정을 반복하며 모든 정점을 방문하게 되면 MST가 구해진다.

 

시작 1번 정점으로 부터 인접한 정점과 가중치를 확인

큐에 넣어주고 1 정점은 방문했음을 표기

 

가장 먼저 큐에서 뽑힌 3정점으로

3정점에서 인접점을 큐에 넣어준다. 이때 1 인접점은 이미 방문했으므로 큐에 넣지 않는다.

 

정점 2에서 확인한 정점을 큐에 다시 넣어준다.

 

다음으로 추출될 데이터는 정점 2 - 가중치 7 이지만

이미 2번 정점은 최소 가중치로 방문이 되었으므로 다음 탐색을 진행한다.

4 정점에서 3 정점은 이미 방문했으므로 큐에 넣지 않는다.

 

위의 그림에서 다음으로 추출될 데이터는 정점 5- 가중치 10 이지만

이미 방문했으므로 다음 탐색으로 건너 뛴다.

 

6으로 가는 최소 가중치는 위의 4-6 경로이다.

이로써 MST 알고리즘을 프림 알고리즘으로 해결하는 방식이다.

 

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

4386번: 별자리 만들기

 

풀이

int stars = int.Parse(Console.ReadLine());

float[,] arr = new float[stars,2];

Dictionary<(float,float),int> visited = new Dictionary<(float, float), int>();

PriorityQueue<(float,float,float),float> pq = 
    new PriorityQueue<(float, float, float), float>();

for (int i = 0; i < stars; i++)
{
    float[] input = Array.ConvertAll(Console.ReadLine().Split(' '),float.Parse);

    arr[i,0] = input[0];
    arr[i,1] = input[1];

    visited.Add((input[0],input[1]),0);
}

pq.Enqueue((arr[0,0],arr[0,1],0),0);

float distance = 0;

while (true)
{
    if(stars <= 0)
        break;

    var temp = pq.Dequeue();

    float cur_x = temp.Item1;
    float cur_y = temp.Item2;
    
    if(visited[(cur_x,cur_y)] == 1)
        continue;

    visited[(cur_x,cur_y)] = 1;
   
    stars--;
    distance += temp.Item3;

    for (int i = 0; i < arr.GetLength(0); i++)
    {
        float temp_x = arr[i,0];
        float temp_y = arr[i,1];

        if(visited[(temp_x,temp_y)] == 1)
            continue;

        float tempDist_x = Math.Abs(cur_x - temp_x);
        float tempDist_y = Math.Abs(cur_y - temp_y);

        float hypotenuse =
        (float)Math.Sqrt(Math.Pow(tempDist_x,2)+Math.Pow(tempDist_y,2));

        pq.Enqueue((temp_x,temp_y,hypotenuse),hypotenuse);
    }
}

System.Console.WriteLine(distance);

 

미흡하거나 개선될수 있는부분이 있다면 답글 남겨주세요