[Algorithm]Baekjoon 1922번 :: 네트워크 연결(크루스칼 알고리즘)

https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

int parents[1001];
 
struct Node
{
    int start;
    int dest;
    int cost;
 
    Node(int _start, int _dest, int _cost) : start(_start),dest(_dest), cost(_cost) {};
};
 
bool cmp(const Node& a, const Node& b)
{
    return a.cost < b.cost;
}
 
int getParent(int node)
{
    if (parents[node] == node) return node; // 자기자신이면 그대로 리턴.
    return parents[node] = getParent(parents[node]);
}
 
void unionParent(int node1, int node2)
{
    node1 = getParent(node1);
    node2 = getParent(node2);
 
    if (node1 < node2) parents[node2] = node1;
    else parents[node1] = node2;
}
 
bool CheckCycle(int node1, int node2)
{
    node1 = getParent(node1);
    node2 = getParent(node2);
 
    if (node1 == node2) return true;
    return false;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    for (int i = 0; i < 1001; i++)
    {
        parents[i] = i;
    }
 
    int nodes = 0;
    int edges = 0;
    int start = 0;
    int dest = 0;
    int cost = 0;
    int sum = 0;
 
    cin >> nodes >> edges;
 
    vector<Node> nv;
 
    for (int i = 0; i < edges; i++)
    {
        cin >> start >> dest >> cost;
        nv.push_back(Node(start, dest, cost));
    }
 
    sort(nv.begin(), nv.end(), cmp);
 
    for (int i = 0; i < nv.size(); i++)
    {
        Node popedNode = nv[i];
 
        if (!CheckCycle(popedNode.start, popedNode.dest))
        {
            unionParent(popedNode.start, popedNode.dest);
            sum += popedNode.cost;
        }
    }
 
    cout << sum;
}

 

크루스칼 기본예제 문제는 이전에 프로그래머스에서 푼 적 있는데, 안까먹으려고 백준에서 비슷한 문제를 다시 풀어봤다. 그리고 문제는 풀지만 실제 시간복잡도 같은거는 머리속에 인지를 잘 안해놨었기 때문에 겸사겸사 풀어본 것도 있다.

크루스칼알고리즘은 기본적으로 가중치값 기준으로 오름차순정렬이 되어있어야 한다.

C++에선 보통 algorithm.h에 포함된 sort함수를 사용하게 될 텐데, 이 함수는 quickSort로 작성되어 있다고 한다.

quickSort의 시간복잡도는 평균적으로 nlogn 이다.(최악의 경우는 n^2 이지만, '평균적'으로 nlogn)

크루스칼에서는 간선의 개수가 n이니까 E logE 라 표현해도 맞는 표현이다.