(2024-11-07) 6 문제 : 백준 - 14950 (정복)

 

처음엔 BFS나 DFS로 최단거리를 찾는 문제인가 했지만, 이 문제의 경우 BFS나 DFS로 하면 왔던 경로를 다시 돌아가야 하는 상황이 생기면서 문제가 발생한다.

 

아무든 최소비용으로 모든 정점을 연결하는 것이 문제의 핵심이고, 다시 생각해보니 크루스칼 알고리즘이 있었다. 크루스칼 알고리즘은 최소신장트리를 찾는 알고리즘으로 위에서 말한 대로 최소비용으로 모든 정점을 연결하는 알고리즘이다.

 

크루스칼 알고리즘을 통해 최소비용을 구하는 것은 그냥 알고리즘을 그대로 적용하면 되니까 어렵지 않다. 다만, 문제에는 간선을 하나 연결할 때마다 증가하는 비용 t가 존재한다. 이 t는 크루스칼 알고리즘을 통해 간선을 하나 처리할 때마다 1씩 더해지는 값을 누적하여 t가 더해질 개수를 구하고 최종적으로 비용에 더해주면 된다.

 

무슨 말이냐면, 간선을 1개 연결할 때엔 간선의 비용이 발생하고, 2개를 연결할 때엔 t가 추가적으로 발생한다. 3개를 연결할 때엔 앞에서 더해진 t와 함께 t가 한 번 더 더해진다.

 

즉, n개의 간선을 연결하면 0 + 1 + 2 + 3 + 4 ..... n - 1만큼의 t가 더해지는 셈인 것이다. 이 개수와 t를 곱해서 크루스칼 알고리즘으로 구한 최소비용에 더해주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int GetParent(std::vector<int>& _Parent, int _Index)
{
    if (_Parent[_Index] != _Index)
    {
        _Parent[_Index] = GetParent(_Parent, _Parent[_Index]);
    }

    return _Parent[_Index];
}

void Union(std::vector<int>& _Parent, int _Left, int _Right)
{
    int LeftParent = GetParent(_Parent, _Left);
    int RightParent = GetParent(_Parent, _Right);

    if (LeftParent < RightParent)
    {
        _Parent[RightParent] = LeftParent;
    }
    else
    {
        _Parent[LeftParent] = RightParent;
    }
}

bool IsCycle(std::vector<int>& _Parent, int _Point1, int _Point2)
{
    return GetParent(_Parent, _Point1) == GetParent(_Parent, _Point2);
}

int main()
{
    Init();

    int NumCity = 0, NumEdge = 0, AddCost = 0;
    std::cin >> NumCity >> NumEdge >> AddCost;

    //비용, X, Y
    std::vector<std::tuple<int, int, int>> Edge(NumEdge);
    for (int i = 0; i < NumEdge; i++)
    {
        std::cin >> std::get<1>(Edge[i]) >> std::get<2>(Edge[i]) >> std::get<0>(Edge[i]);
        
        std::get<1>(Edge[i])--;
        std::get<2>(Edge[i])--;
    }

    std::sort(Edge.begin(), Edge.end());

    int SumCost = 0;
    int EdgeCount = 0;
    int AddCount = 0;

    std::vector<int> Parent(NumCity);
    for (int i = 0; i < NumCity; i++)
    {
        Parent[i] = i;
    }
    
    for (int i = 0; i < NumEdge; i++)
    {
        if (IsCycle(Parent, std::get<1>(Edge[i]), std::get<2>(Edge[i])) == false)
        {
            Union(Parent, std::get<1>(Edge[i]), std::get<2>(Edge[i]));
            SumCost += std::get<0>(Edge[i]);
            
            EdgeCount += AddCount;
            AddCount++;
        }
    }

    SumCost += AddCost * EdgeCount;

    std::cout << SumCost;

    return 0;
}