[C++] 프로그래머스 섬 연결하기 프림알고리즘

#include <string>
#include <vector>
#include <queue>

using namespace std;

//0left 1right 2weight
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    //weight, 간선번호
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<bool> visited(n, false);

    //0부터 시작
    for (int i = 0; i < costs.size(); i++)
    {
        int left = costs[i][0];
        int right = costs[i][1];
        int weight = costs[i][2];

        if (left == 0)
        {
            visited[0] = true;
            pq.push({ weight, right });
        }
        else if (right == 0)
        {
            visited[0] = true;
            pq.push({ weight, left });
        }
    }

    while (!pq.empty())
    {
        int currNode = pq.top().second;     //현재 정점
        int currWeight = pq.top().first;    //이전 정점인곳에서 현재 정점까지의 거리
        pq.pop();

        if (visited[currNode] == false) //현재 정점이 방문하지 않았을 때
        {
            answer += currWeight;   //현재 정점까지의 거리를 추가한다.
            visited[currNode] = true;   //현재 정점을 방문한 곳으로 추가한다.

            for (int i = 0; i < costs.size(); i++)  //현재 정점에서 갈 수 있는 간선들을 확인
            {
                int nextLeft = costs[i][0];
                int nextRight = costs[i][1];
                int nextWeight = costs[i][2];

                //다음으로 갈 정점을 넣어준다. (근접 정점)
                if (currNode == nextLeft && visited[nextRight] == false)
                    pq.push({ nextWeight, nextRight });
                else if (currNode == nextRight && visited[nextLeft] == false)
                    pq.push({ nextWeight, nextLeft });
            }
        }
    }

    return answer;
}

풀이

1. 방향이 없지만 한 방향으로만 그래프가 주어지므로 이것을 활용한다.

2. 0부터 시작하기 위해 start - end, end - start일 수도 있으므로 둘 다 확인을 하여 다음 정점을 넣어준다.

3. 우선순위 큐를 활용하여 가중치가 낮은 순으로 순회한다.

4. 방문한 곳을 방문하지 않는다.

5. 다음 정점에 도착했다면 현재 정점이 된다.

6. 현재 정점 도착하였다면 도착한 곳이지 않을 때만 가중치와 방문표시를 해준다.

7. 현재 정점에서 다음 정점으로 가는 간선들을 확인하는데 다음 정점이 방문하지 않은 곳만 추가해준다.

 

- 최소신장트리를 이용하여 푸는 문제인데 그 중 프림알고리즘을 채택하였습니다.

 

 

프림알고리즘 정보 : https://yabmoons.tistory.com/362

[ 프림 알고리즘 ] 개념과 구현방법 (C++)

 

https://programmers.co.kr/learn/courses/30/lessons/42861#

코딩테스트 연습 - 섬 연결하기