[Algorithm] Baekjoon 16398번 : 행성 연결

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

16398번: 행성 연결

struct Node
{
    int start;
    int end;
    int cost;
};
 
int n;
 
int parents[1000];
bool visited[1000][1000] = { false };
vector<Node> costs;
 
int GetParent(int node)
{
    if (parents[node] == node) return node;
    return parents[node] = GetParent(parents[node]);
}
 
bool CompareParent(int a, int b)
{
    return GetParent(a) == GetParent(b);
}
 
void UnionSet(int a, int b)
{
    a = GetParent(a);
    b = GetParent(b);
 
    if (a < b) parents[b] = a;
    else parents[a] = b;
}
 
bool cmp(const Node& a, const Node& b)
{
    return a.cost < b.cost;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    long long answer = 0;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            int cost;
            cin >> cost;
            if (i == j) continue;
            if (visited[j][i]) continue;
 
            visited[i][j] = true;
            costs.push_back({ i,j,cost });
        }
    }
 
    for (int i = 0; i < n; ++i) parents[i] = i;
 
    sort(costs.begin(), costs.end(), cmp);
 
    for (int i = 0; i < costs.size(); ++i)
    {
        if (!CompareParent(costs[i].start, costs[i].end))
        {
            UnionSet(costs[i].start, costs[i].end);
            answer += costs[i].cost;
        }
    }
 
    cout << answer;
}

최소신장트리(MST)를 만들어야하는 기본예제수준의 문제이다.

크루스칼이나 프림 둘 중 하나를 이용해서 만들 수 있는데, 나는 크루스칼로 만들었다.

시간복잡도는 가중치를 오름차순으로 만들기 위한 정렬의 시간복잡도에 거의 의지한다고 보면 된다.

STL의 sort의 시간복잡도는 N log N인데, 여기서 N은 간선의 개수니까 E log E 라고 표현할 수 있다.