[백준] 1922 네트워크 연결, C++

1922번: 네트워크 연결

문제 요약

모든 컴퓨터를 연결하는데 필요한 최소 비용을 출력한다.

접근

1. BFS

최소 비용이면 BFS라고 생각할수 있겠지만 시작점에서 특정 지점까지의 최소 거리이므로 조건과 맞지않다. (몇몇 조건은 만족할수 있다.)

2. MST(Minimum Spanning Tree) 최소신장트리

사용된 간선들의 가중치 합이 최소인 트리이다.
신장트리를 만들때 최소의 간선을 사용해서 모든 노드를 방문해야 하고, 사이클을 만들지 않아야한다.

1. Kruskal

• 낮은 비용의 간선부터 차례로 선택함
• 사이클이 생기는 간선은 제거함(cycle이 만들어지는지 확인 필요, ex. union-find)
• int kruskal() // pq sorted by weight { int ret = 0; while(!pq.empty()) { EDGE cur = pq.top(); pq.pop(); // making a cycle, skip; if (myFind(cur.s) == myFind(cur.e)) continue; myUnion(cur.s, cur.e); ret += cur.w; } return ret; }

2. Prim

• 방문한 노드의 인접한 간선을 추가함.
• 가중치가 가장 작은 간선을 선택해서 그다음 노드에 방문함.
• 모든 노드를 반복할때까지 반복
• int prim() { int ret = 0; priority_queue<pair<int, int>> pq; pq.push({0, 1}); while (!pq.empty()) { pair<int,int> cur = pq.top(); pq.pop(); if (visit[cur.second]) continue; visit[cur.second] = 1; ret += (-cur.first); // default sorting by max value for (auto adj: adj_list[cur.second]) { pq.push({-adj.second, adj.first}); // default sorting by max value } } return ret; }

전체 코드

Kruskal

#include <iostream>
#include <vector>
#include <queue> // priority_queue
using namespace std;

#define N_MAX 1001

typedef struct {
int w;
int s;
int e;
} EDGE;

struct compare {
    bool operator() (const EDGE A, const EDGE B)
    {
        return A.w > B.w;
    }
};

priority_queue <EDGE, vector<EDGE>, compare> pq;

int N, M;
int p[N_MAX]; //parent(root)
int r[N_MAX]; //rank

void init()
{
    cin >> N;
    cin >> M;
    int s, e, w;
    for (size_t i = 0; i < M; i++)
    {
        cin >> s >> e >> w;
        pq.push({w, s, e});
    }
    // for checking cycle
    for (size_t i = 0; i <= N; i++)
        p[i] = i;
}

int myFind(int A)
{
    if (p[A] == A) return A;  
    p[A] = myFind(p[A]);
    return p[A];
}

void myUnion(int A, int B)
{
    A = myFind(A);
    B = myFind(B);
    if (A == B) return;
    if (r[A] < r[B])
        p[A] = B;
    else
    {
        p[B] = A;
        if (r[A] == r[B])
            r[A]++;
    }
}

int kruskal() // pq sorted by weight
{
    int ret = 0; // 100,000*10,000 = 1,000,000,000

    while(!pq.empty())
    {
        EDGE cur = pq.top();
        pq.pop();

        // making a cycle, skip;
        if (myFind(cur.s) == myFind(cur.e)) continue;
        myUnion(cur.s, cur.e);
        ret += cur.w;
    }

    return ret;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    init();
    cout << kruskal() << endl;
    return 0;
}

Prim

#include <iostream>
#include <vector>
#include <queue> // priority queue

using namespace std;

#define N_MAX 1001

int N, M;
int visit[N_MAX];
vector<vector<pair<int,int>>> adj_list;

void init()
{
    cin >> N;
    cin >> M;
    adj_list.reserve(N+1);
    int s,e,w;
    for (size_t i = 0; i < M; i++)
    {
        cin >> s >> e >> w;
        adj_list[s].push_back({e, w});
        adj_list[e].push_back({s, w});
    }
}

int prim()
{
    int ret = 0;
    priority_queue<pair<int, int>> pq;
    pq.push({0, 1});
    while (!pq.empty())
    {
        pair<int,int> cur = pq.top();
        pq.pop();

        if (visit[cur.second]) continue;
        visit[cur.second] = 1;
        ret += (-cur.first); 
            // default sorting by max value
        for (auto adj: adj_list[cur.second])
        {
            pq.push({-adj.second, adj.first});
                // default sorting by max value
        }

    }
    return ret;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    init();
    cout << prim() << endl;
    return 0;
}