[백준][C++] 10432: 전기가 부족해

문제

10423번: 전기가 부족해

풀이

최소 스패닝 트리, 크루스칼 알고리즘 문제이다. 

 

직접 작성한 코드는 모든 노드의 부모 노드가 발전소 노드일 때까지 크루스칼 알고리즘을 진행하며, 각 노드가 이미 발전소와 연결되어있는 간선은 선택하지 않는 방식으로 작성했다. 

 

다른 코드를 보니, 발전소 노드를 미리 하나의 그룹으로 묶어서 크루스칼 알고리즘을 진행하는 방식으로 문제를 해결하였다. 이렇게 하면 모든 노드가 발전소와 연결되었는지 확인할 필요도 없고, 한 노드가 다른 발전소와 중복 연결될 일이 없어진다.

 

코드

직접 작성

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

using namespace std;

typedef struct
{
    int v1;
    int v2;
    int dist;
}edge;
vector<edge> edges;
int parent[1001];
bool elect[1001];

bool compare(edge a, edge b)
{
    return a.dist < b.dist;
}

int getParent(int n)
{
    if (n == parent[n])
    {
        return n;
    }
    return getParent(parent[n]);
}

bool cycle(int n1, int n2)
{
    n1 = getParent(n1);
    n2 = getParent(n2);
    return n1 == n2;
}

void Union(int n1, int n2)
{
    int p1 = getParent(n1);
    int p2 = getParent(n2);
    if (elect[p1])
    {
        parent[p2] = p1;
        return;
    }
    else if (elect[p2])
    {
        parent[p1] = p2;
        return;
    }

    if (p1 < p2)
    {
        parent[p2] = p1;
    }
    else
    {
        parent[p1] = p2;
    }
}

bool allElected(int N)
{
    for (int i = 1; i <= N; ++i)
    {
        int p = getParent(i);
        if (!elect[p])
        {
            return false;
        }
    }

    return true;
}

bool isElected(int n)
{
    n = getParent(n);
    return elect[n];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, K;
    cin >> N >> M >> K;

    for (int i = 0; i < K; ++i)
    {
        int temp;
        cin >> temp;
        elect[temp] = true;
    }

    for (int i = 0; i < M; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;

        edges.push_back({ u, v, w });
    }

    // 크루스칼 알고리즘 실시
    for (int i = 1; i <= N; ++i)
    {
        parent[i] = i;
    }

    sort(edges.begin(), edges.end(), compare);

    int answer = 0;
    for (auto edge : edges)
    {
        if (allElected(N))
        {
            break;
        }

        if (!cycle(edge.v1, edge.v2) && !(isElected(edge.v1) && isElected(edge.v2)))
        {
            answer += edge.dist;
            Union(edge.v1, edge.v2);
        }
    }

    cout << answer;

    return 0;
}

 

미리 발전소를 연결하는 방법

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

using namespace std;

typedef struct
{
    int v1;
    int v2;
    int dist;
}edge;
vector<edge> edges;
int parent[1001];
vector<int> elect;

bool compare(edge a, edge b)
{
    return a.dist < b.dist;
}

int getParent(int n)
{
    if (n == parent[n])
    {
        return n;
    }
    return getParent(parent[n]);
}

bool cycle(int n1, int n2)
{
    n1 = getParent(n1);
    n2 = getParent(n2);
    return n1 == n2;
}

void Union(int n1, int n2)
{
    int p1 = getParent(n1);
    int p2 = getParent(n2);

    if (p1 < p2)
    {
        parent[p2] = p1;
    }
    else
    {
        parent[p1] = p2;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, K;
    cin >> N >> M >> K;

    for (int i = 0; i < K; ++i)
    {
        int temp;
        cin >> temp;
        elect.push_back(temp);
    }

    for (int i = 1; i <= N; ++i)
    {
        parent[i] = i;
    }

    // 발전소 노드는 미리 하나의 그룹으로 만들어 놓는다.
    for (int i = 1; i < K; ++i)
    {
        Union(elect[0], elect[i]);
    }

    for (int i = 0; i < M; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;

        edges.push_back({ u, v, w });
    }    

    sort(edges.begin(), edges.end(), compare);

    // 크루스칼 알고리즘 실시
    int answer = 0;
    for (auto edge : edges)
    {

        if (!cycle(edge.v1, edge.v2))
        {
            answer += edge.dist;
            Union(edge.v1, edge.v2);
        }
    }

    cout << answer;

    return 0;
}