[BOJ알고리즘, C++]#1647_도시 분할 계획, MST, 최소 신장 트리, 크루스칼, 프림, 솔린

 

#1. 문제

 

 

---

 

#2. 풀이

 

2-1. 최소 신장 트리

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

 

Details

 

[개념] : 최소 신장 트리는 무방향 그래프 내 가중치의 합이 최소가 되는 최소 신장 트리입니다.
[특징] : 최소한의 간선, 최소 비용(최소 가중치의 합), 그리고 모든 정점 연결
[구현] : 크루스칼(Kruskal) 알고리즘, 프림(Prim) 알고리즘, 그리고 솔린(Sollin) 알고리즘

 

2-2. 크루스칼 알고리즘

크루스칼(Kruskal) 알고리즘은 MST를 구현하는 알고리즘 중 하나로, 그리디 알고리즘을 활용합니다. 크루스칼 알고리즘은 '간선 중심'의 MST 알고리즘으로, 간선 목록을 '가중치 기준' 오름차순 정렬하고, 정렬된 간선 목록을 순회하며 Union-Find 연산을 수행합니다. 이를 통해, 최종적으로 주어진 가중치 그래프로부터 MST를 구성합니다.

 

2-3. 프림 알고리즘

프림(Prim) 알고리즘은 MST를 구현하는 알고리즘 중 하나로, 그리디 알고리즘을 활용합니다. 프림 알고리즘은 '정점 중심'의 MST 알고리즘으로, 임의의 정점을 시작으로 어떤 정점의 '인접 정점'들을 순회하며 서로 연결된 간선 정보를 '가중치 기준 최소 힙(우선순위 큐)'에 삽입합니다. 이를 통해, 최종적으로 주어진 가중치 그래프로부터 MST를 구성합니다.

 

2-4. 솔린 알고리즘

솔린(Sollin) 알고리즘은 MST를 구성하는 알고리즘 중 하나로, 그리디 알고리즘을 활용합니다. 솔린 알고리즘은 '집합 중심'의 MST 알고리즘으로, 간선 목록을 순회하며 각 간선을 구성하는 시작 노드와 도착 노드가 속한 집합의 최소 가중치 간선을 찾고, 다시 각 집합의 최소 가중치 간선들을 모아놓은 데이터 목록을 순회하며 Union-Find 연산 수행 및 MST를 구성할 간선들을 추가합니다. 최종적으로, 가중치 그래프로부터 MST를 구성합니다.

 

2-5. 최소 신장 트리 중에서도 가중치가 가장 높은 간선을 제거하자!

1. 먼저, 문제는 분리된 두 마을 모두 임의의 두 집 사이에 경로가 항상 존재함과 동시에 필요 없는 나머지 길들은 제거 하면서도 두 개의 마을로 분할하고자 한다. 즉, 주어진 그래프로부터 '최소 신장 트리(모든 정점을 연결함과 동시에 최소한의 간선으로 구성된 부분 그래프)'를 구성하고, 남아있는 길들의 유지비를 최소로 하기 위해 최소 신장 트리를 구성하는 간선들 중 가중치가 가장 높은 간선을 제거함으로써 두 개의 최소 신장 트리로 분할해야 합니다.
2. MST 알고리즘(크루스칼, 프림, 솔린)을 수행함과 동시에, MST를 구성하는 간선들 중 가중치가 최대인 간선을 기억해두었다가, 알고리즘을 모두 수행한 후 최대 가중치를 빼주면 됩니다.

 

---

 

#3. 코드

 

3-1. 크루스칼

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int N, M;

// #1. 간선 구조체
struct Edge
{
    int from, to, weight;
    bool operator<(const Edge &other)
    {
        return weight < other.weight;
    }
};

// #2. Find 연산
int Find(int x, vector<int> &parent)
{
    if (parent[x] != x)
    {
        parent[x] = Find(parent[x], parent);
    }

    return parent[x];
}
// #3. Union 연산
void Union(int rootX, int rootY, vector<int> &parent, vector<int> &rank)
{

    if (rank[rootX] > rank[rootY])
    {
        parent[rootY] = rootX;
    }
    else if (rank[rootX] < rank[rootY])
    {
        parent[rootX] = rootY;
    }
    else
    {
        parent[rootX] = rootY;
        rank[rootY]++;
    }
}

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

    cin >> N >> M;

    // #1. 간선 목록
    vector<Edge> edges(M);

    // #2. 간선 목록 구성
    for (int i = 0; i < M; ++i)
    {
        cin >> edges[i].from >> edges[i].to >> edges[i].weight;
    }

    // #3. 간선 목록을 가중치 기준 오름차순 정렬
    sort(begin(edges), end(edges));

    // #4. 크루스칼
    vector<int> parent(N + 1);
    vector<int> rank(N + 1, 0);

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

    int MSTWeight = 0;
    int maxWeight = INT_MIN;
    for (const auto &edge : edges)
    {
        // Find 연산 : 대표 노드 찾기
        int rootX = Find(edge.from, parent);
        int rootY = Find(edge.to, parent);

        // Union 연산 : 두 대표 노드의 트리가 서로소 집합일 경우, 하나로 합침
        if (rootX != rootY)
        {
            Union(rootX, rootY, parent, rank);
            // MST 목록에 추가
            MSTWeight += edge.weight;
            if (edge.weight > maxWeight)
            {
                maxWeight = edge.weight;
            }
        }
    }

    // MST 목록 중 가장 큰 값은 제외
    cout << MSTWeight - maxWeight;

    return 0;
}

 

3-2. 프림

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <climits>
using namespace std;

int N, M;

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

    cin >> N >> M;

    // 간선 목록, pair < 가중치, 인접 정점 >
    vector<vector<pair<int, int>>> graph(N + 1);
    // 방문 여부
    vector<bool> visited(N + 1, false);
    // 우선순위 큐, 간선의 가중치 기준 최소 힙 구성
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // MST 가중치의 합
    int MSTWeight = 0;
    // MST 목록 중 최대 가중치
    int maxWeight = INT_MIN;
    // 그래프 구성
    while (M--)
    {
        int from, to, weight;
        cin >> from >> to >> weight;

        graph[from].push_back({weight, to});
        graph[to].push_back({weight, from});
    }

    // 솔린 알고리즘 수행
    pq.push({0, 1});
    while (!pq.empty())
    {
        int node = pq.top().second;
        int weight = pq.top().first;
        pq.pop();

        if (visited[node])
            continue;
        // 방문 여부 체크
        visited[node] = true;
        // 최소 가중치의 합
        MSTWeight += weight;
        // MST의 최대 가중치 값 갱신
        if (maxWeight < weight)
            maxWeight = weight;
        // 현재 정점의 간선 목록 순회
        for (const auto &edge : graph[node])
        {
            if (!visited[edge.second])
            {
                pq.push(edge);
            }
        }
    }

    cout << MSTWeight - maxWeight;

    return 0;
}

 

3-3. 솔린

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

int N, M;

// #1. 간선 구조체
struct Edge
{
	int from, weight, to;

	bool operator<(const Edge& RightEdge)
	{
		return weight < RightEdge.weight;
	}
};

// #2. Find 연산
int Find(int x, vector<int>& parent)
{
	if (parent[x] != x)
	{
		parent[x] = Find(parent[x], parent);
	}

	return parent[x];
}
// #3. Union 연산
void Union(int rootX, int rootY, vector<int>& parent, vector<int>& rank)
{

	if (rank[rootX] > rank[rootY])
	{
		parent[rootY] = rootX;
	}
	else if (rank[rootX] < rank[rootY])
	{
		parent[rootX] = rootY;
	}
	else
	{
		parent[rootX] = rootY;
		rank[rootY]++;
	}

}

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

    cin >> N >> M;
    
    vector<Edge> edges(M);
    
    for(int i=0; i<M; ++i)
        cin >> edges[i].from >> edges[i].to >> edges[i].weight;
    
    // 부모 노드 목록, 최소 가중치 목록, rank 목록
    vector<int> parent(N+1), minWeight(N+1), rank(N+1, 0);
    // 컴포넌트 개수, MST 가중치 합, MST 가중치 중 최대 가중치
    int components = N;
    int MSTWeight = 0;
    int maxWeight = INT_MIN;
    
    // 부모 노드 목록 초기화
    for(int i=1; i<=N; ++i)
        parent[i] = i;
    
    // 솔린 알고리즘 수행
    while(components > 1)
    {
        // 최소 가중치 목록 -1로 초기화
        fill(begin(minWeight), end(minWeight), -1);
        
        // 가중치 목록 순회, 최소 가중치 목록 갱신
        for(int i=0; i<M; ++i)
        {
            int comp1 = Find(edges[i].from, parent);
            int comp2 = Find(edges[i].to, parent);
            
            if(comp1 == comp2)
                continue;
            
            if(minWeight[comp1] == -1 || edges[minWeight[comp1]].weight > edges[i].weight)
                minWeight[comp1] = i;
            if(minWeight[comp2] == -1 || edges[minWeight[comp2]].weight > edges[i].weight)
                minWeight[comp2] = i;
        }
        
        // 최소 가중치가 갱신된 집합에 대해 Union 연산 수행
        for(int i=1; i<=N; ++i)
        {
            if(minWeight[i] != -1)
            {
                int comp1 = Find(edges[minWeight[i]].from, parent);
                int comp2 = Find(edges[minWeight[i]].to, parent);
                
                if(comp1 == comp2)
                    continue;
                // Union 연산
                Union(comp1, comp2, parent, rank);
                // 컴포넌트 -1 차감
                components--;
                // MST 가중치 합에 더해줍니다.
                MSTWeight += edges[minWeight[i]].weight;
                // MST 간선 목록 중 가중치가 최대일 경우 갱신
                if(maxWeight < edges[minWeight[i]].weight)
                    maxWeight = edges[minWeight[i]].weight;
            }
        }
    }
    
    cout << MSTWeight - maxWeight;
    
    return 0;
}

 

---