[BOJ, C++]#1368_물 대기, 최소 스패닝 트리, 최소 신장 트리, 크루스칼, 최소 신장 트리의 가상 노드, 가상 노드 활용

#1. 문제

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

 

---

 

#2. 풀이

 

1. 최소 신장 트리

[자료구조]#6_그래프

최소 신장 트리는 트리의 한 종류로, 그래프의 모든 정점을 최소한의 간선으로 순환 구조 없이 연결하는 부분 그래프입니다.

 

2. 크루스칼 알고리즘

[자료구조]#6_그래프

크루스칼 알고리즘은 최소 신장 트리를 구성하는 알고리즘 중 하나로, 무방향 가중치 그래프에서 간선을 가중치 기준으로 오름차순 정렬하여, 최소 가중치를 갖는 간선부터 차례대로 선택하며 최소 신장 트리를 구성합니다. 

크루스칼 알고리즘은 Union-Find 연산을 활용하여 선택한 간선의 출발 정점과 도착 정점의 서로소 관계를 확인하고, 합집합으로 구성하며 최종적으로 하나의 신장 트리를 구성합니다.

 

3. '우물 파기'는 가상의 노드와 연결된 간선의 가중치로 가정하자!

1. 먼저, 최소 신장 트리 구성 시 각 노드가 '우물 파기'를 하는 경우를 고려하기 위해, 가상의 노드를 추가하고(0번 정점) 각 정점이 해당 정점으로 연결되는 간선의 가중치를 각 정점에서 '우물 파기'하는 비용으로 가정합니다.
2. 그리고, 크루스칼 알고리즘을 수행하여 각 논에 물을 대는 최소 비용을 계산해 줍니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/1368
*   @문제: 물대기
*   @설명
        1. 최소 스패닝 트리
        2. 가상의 노드 추가, 우물 파기 할 경우 자기 자신에 대하여 간선이 구성되어 
            기존의 최소 신장 트리 알고리즘이 힘들어진다. 따라서, 자기 자신에 대한
            간선 구성을 임의의 가상 노드를 두어, U -> 가상 노드 간선으로 구성하여
            기존의 최소 신장 트리 수행.
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge
{
    int u, v, w;
    Edge(int u, int v, int w)
    {
        this->u = u;
        this->v = v;
        this->w = w;
    }
    const bool operator<(const Edge& Other)
    {
        return w < Other.w;
    }
};
int N;
vector<Edge> edges;
int Find(int x, vector<int>& parent)
{
    if(parent[x] != x)
    {
        parent[x] = Find(parent[x], parent);
    }
    return parent[x];
}
void Union(int rootY, int rootX, vector<int>& parent, vector<int>& rank)
{
    if(rank[rootY] > rank[rootX])
    {
        parent[rootX] = rootY;
    }
    else if(rank[rootX] > rank[rootY])
    {
        parent[rootY] = rootX;
    }
    else
    {
        parent[rootX] = rootY;
        rank[rootY]++;
    }
}
void kruskal()
{
    vector<int> parent(N+1);
    vector<int> rank(N+1, 0);
    int MST = 0;
    //@부모 목록
    for(int i=0; i<=N; ++i)
    {
        parent[i] = i;
    }
    //@가중치 기준 오름차순 정렬
    sort(begin(edges), end(edges));
    for(auto edge : edges)
    {
        int rootY = Find(edge.u, parent);
        int rootX = Find(edge.v, parent);
        if(rootX != rootY)
        {
            MST += edge.w;
            Union(rootY, rootX, parent, rank);
        }
    }
    cout << MST;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    //@우물파기
    for(int i=1; i<=N; ++i)
    {
        int w;
        cin >> w;
        edges.push_back(Edge(i, 0, w));
    }
    //@물 대기
    for(int i=1; i<=N; ++i)
    {
        for(int j=1; j<=N; ++j)
        {
            int w;
            cin >> w;
            if(w !=0) edges.push_back(Edge(i, j, w));
        }
    }
    //@크루스칼
    kruskal();
    return 0;
}

 

---