[Inflearn] 원더랜드(Prim MST 알고리즘 : priority_queue 활용)(c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

이전 문제와 동일하지만 다른 방법으로 풀어보자.

Prim 알고리즘.. 도 처음 들어본다..

ㅇPrim 알고리즘

  - 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법

  - Kruskal 알고리즘은 간선을 기준으로 간선을 선택에 확장해 나갔다면 Prim 알고리즘은 임의의 시작 정점을 선택하고

    거기서부터 계속 연결관계를 보며 정점을 선택해 확장.

ㅇ 동작

  1. 시작 단계에서 시작 정점만이 MST 집합에 포함

  2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장

     (가장 낮은 가중치를 먼저 선택)

  3. 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복

그렇다면, 

먼저 각 정점들과 연결된 인접 리스트를 만들어보자.

여기서는 양방향 그래프를 그려야 하므로 그림으로 그리기에 너무 많다.. 하핳

그림은 패스하고 머릿속에 그려보자!

머릿속에 그리기 복잡하다면 인접 리스트의 구조를 확인하자!

임의의 시작 정점을 1로 하고 동작시켜보자.

(1, 0)

도착 정점, 가중치 정보를 priority_queue 에 넣어야 한다. 

(도착 정점과 가중치 정보를 저장하는 구조체가 필요할 것 같다)

struct Info

{

int v;

int wt;

}

(1, 0)

queue 가 빌 때까지 반복해보자 

top() 을 호출하여 도착 정점 1을 얻고, sum에 가중치 0을 더한 후 pop() 시켜준다.

그 후 1 과 연결된 정점을 priority_queue 에 넣는다.

(2, 12)  (9,25)

일단 priority_queue 의 최소힙 기준을 가중치로 하기 위해서

구조체에 operator 함수가 필요하겠다.

struct Info

{

int v;

int wt;

Info(int a, int b)

{

int v = a;

int wt = b;

}

bool operator<(const Info &d) const

{

return wt>d.wt;

}

};

이렇게 구조체를 만들어 놓으면

priority_queue 는 가중치 기준 오름차순으로 트리를 형성할 것이다.

그래야만 한다..ㅋㅋㅋ

(2, 12)  (9,25)

그렇다면 여기서 top() 을 호출하면

도착 정점 2와 가중치 12를 얻을 수 있다.

대략적인 코드는 아래와 같이 나올 것 같다.

while(!pQ.empty())

{

x = pQ.top().v;

sum += pQ.top().wt;

pQ.opo();

for(i = 0; i < road[x].size(); i++

pQ.push(road[x][i]);

]

계속 해보자.

도착 정점 2를 얻었으니, 또 정점 2와 연결된 정점을 push() 해준다.

가중치 기준 오름차순으로 트리가 형성되므로 아래와 같이 될 것이다.

여기서 이미 방문한 정점을 표시해줘야 할 것 같다.

방문한 정점을 또 방문하면 안 되므로..

while(!pQ.empty())

{

while(true)

{

x = pQ.top().v;

if(ch[x] == 0)

{

sum += pQ.top().wt;

ch[x] = 1;

pQ.opo();

break;

}

else

pQ.pop();

}

for(i = 0; i < road[x].size(); i++

pQ.push(road[x][i]);

]

마찬가지로 top() 을 호출해서

기준 정점 9 와 가중치 8을 얻었다.

현재까지 1, 2 번 정점을 방문하였으므로 9번 정점을 방문할 수 있다.

그렇다면 마찬가지로 9번 정점과 연결된 정점들을 push 해준다.

(3,10) (8, 17) (9,25)...

이정도면 이해가 갔으리라 생각하다.

코드 설명에서 더 자세히 설명하고

이 과정을 코드로 옮겨보ㅈㅏ!

#. Code

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int cost = 0, ch[101];
 
struct Info
{
    int v;
    int wt;
 
    Info(int a, int b)
    {
        v = a;
        wt = b;
    }
 
    bool operator<(const Info& d) const
    {
        return wt > d.wt;
    }
};
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int v, e, i, a, b, c, x;
    vector<Info> road[101];
    priority_queue<Info> pQ;
 
    scanf("%d %d", &v, &e);
    for (i = 0; i < e; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
 
        road[a].push_back(Info(b, c));
        road[b].push_back(Info(a, c));
    }
 
    pQ.push(Info(1, 0));
 
    while(!pQ.empty())
    {
        while(!pQ.empty())
        {
            x = pQ.top().v;
 
            if (ch[x] == 0)
            {
                cost += pQ.top().wt;
                ch[x] = 1;
                pQ.pop();
 
                break;
            }
            else
                pQ.pop();
        }
 
        for (i = 0; i < road[x].size(); i++)
            if (ch[road[x][i].v] == 0)
                pQ.push(Info(road[x][i].v, road[x][i].wt));
    }
 
    printf("%d\n", cost);
 
    return 0;
}

계속 답이 잘못 나와서 로직에 문제가 있나 디버깅을 하는데,,

알고보니 코드를 수정하면서 값을 잘못 저장하고 있었닼ㅋㅋㅋ

이런..

line 9~24) 도착 정점과 가중치를 저장하기 위한 구조체를 만들었다.

        line 14~18) 구조체 생성자

   line 20~24) priority_queue 에서 가중치 기준 최소힙 트리를 만들기 위해 operator 를 오버로딩해주었다.

line 35~41) 인접 리스트를 생성하는데 양방향 그래프로 생성하였다. 

지금까지가 세팅이고 이제부터가 시작이다.

line 43) 먼저 임의의 시작 정점 (1, 0) 을 priority_queue 에 push 해준다.

line 45~66) 핵심 동작 부분(?) 이라고 할 수 있겠다. pQ 가 빌 때까지 반복한다.

    line 47~61) pQ가 빌 때까지 마찬가지로 반복하는데 

line 49) 먼저 pQ에서 top 의 정점을 확인한다.

line 51~58) 확인한 정점이 방문하지 않은 정점이라면, 이 정점에 해당하는 가중치를 누적시키고

    check 배열에 방문을 기록한 후 다 확인하였으므로 pop() 시키고 break.

line 59~61) 이미 방문한 정점이라면 그냥 pop() 해버리고 다시 pQ를 확인한다.

    line 63~65) 최근 방문한 정점과 연결된 정점들을 확인한다.

line 64) 만일 이미 방문한 정점이라면 굳이 pQ에 넣어줄 필요가 없다.

line 65) 방문하지 않은 정점이라면 pQ에 해당 정점의 정보를 push() 해준다.

ㅇ 코드 간결화

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int cost = 0, ch[101];
 
struct Info
{
    int v;
    int wt;
 
    Info(int a, int b)
    {
        v = a;
        wt = b;
    }
 
    bool operator<(const Info& d) const
    {
        return wt > d.wt;
    }
};
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int v, e, i, a, b, c, tmpV, tmpCost;
    vector<Info> road[101];
    priority_queue<Info> pQ;
 
    scanf("%d %d", &v, &e);
    for (i = 0; i < e; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
 
        road[a].push_back(Info(b, c));
        road[b].push_back(Info(a, c));
    }
 
    pQ.push(Info(1, 0));
 
    while(!pQ.empty())
    {
        Info tmpInfo = pQ.top();
        pQ.pop();
 
        tmpV = tmpInfo.v;
        tmpCost = tmpInfo.wt;
 
        if (ch[tmpV] == 0)
        {
            cost += tmpCost;
            ch[tmpV] = 1;
            
            for (i = 0; i < road[tmpV].size(); i++)
                if (ch[road[tmpV][i].v] == 0)
                    pQ.push(Info(road[tmpV][i].v, road[tmpV][i].wt));
        }
    }
 
    printf("%d\n", cost);
 
    return 0;
}

아직도 많이 부족하지만 그래도 점점 나아지고 있는(?)게 보여서

뿌듯하구만~!

#. Other code

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
 
int ch[30];
 
struct Edge{
    int e;
    int val;
    Edge(int a, int b){
        e=a;
        val=b;
    }
    bool operator<(const Edge &b)const{
        return val>b.val;
    }
};
 
int main(){
    priority_queue<Edge> Q;
    vector<pair<int, int> > map[30];
    int i, n, m, a, b, c, res=0;
    scanf("%d %d", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%d %d %d", &a, &b, &c);
        map[a].push_back(make_pair(b, c));    
        map[b].push_back(make_pair(a, c));
    }
    Q.push(Edge(1, 0));
    while(!Q.empty()){
        Edge tmp=Q.top();
        Q.pop();
        int v=tmp.e;
        int cost=tmp.val;
        if(ch[v]==0){
            res+=cost;
            ch[v]=1;
            for(i=0; i<map[v].size(); i++){
                if(ch[map[v][i].first]==0){
                    Q.push(Edge(map[v][i].first, map[v][i].second));
                }
            }
        }
        
    }
    printf("%d\n", res);
    return 0;
}

로직은 동일하나 역시나 강사님이 코드가 훨씬 깰꿈하다..

나는 복잡시럽게 while(!Q.empty) 를 두 개나 써주었는데 하나만으로도 짤 수 있었다.

뭐 상관없기야 하지만 굳지 나처럼 짤 필요는 없었다.

그리고 top() 에서 구조체를 return 받는게 더 편할 것 같다.

구조체 변수를 생각을 못 했다.. 하핳

구조체 특성도 잘 이용해보자..!

#. Result

  - Input --------------------------------------------------------

9 12 

1 2 12 

1 9 25 

2 3 10 

2 8 17 

2 9 8 

3 4 18 

3 7 55 

4 5 44 

5 6 60 

5 7 38 

7 8 35 

8 9 1

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

  - Output --------------------------------------------------------

196

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