https://www.acmicpc.net/problem/1197
문제
> 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
> 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.접근
이 문제는 MST라고 하는 최소 스패닝 트리를 구현하는 문제이다.
푸는 방법은 두 가지가 있다고 한다.
하나는 prim을 사용하는 것과 하나는 kruskal알고리즘을 사용하는 것이다.
먼저 kruskal 알고리즘을 사용하였다.
Kruskal 알고리즘의 기본 방식은 모든 간선 중 가중치가 가장 작은 간선부터 선택하되, 사이클이 생기면 해당 간선을 버리고 다음 작은 간선을 선택하는 것이다.
사이클의 처리에 대해선 Union과 Find를 사용한다고 한다.
각 정점에 대해 parent라고 하는 배열로 각각의 꼬리표를 달아주고 서로 어떤 집합에 속해있는지 나타내주는것이다.
처음엔 모든 정점이 서로 연결되어있지 않으므로 이 꼬리표가 다 다른 각자의 집합에 속해있다.
이제 가중치가 제일 작은 간선을 선택해가며 정점을 연결하면 어떤 두 정점이 연결되면 둘은 서로 같은 집합에 포함되어있다고 표시해줘야한다.
그래서 Union을 이용해 이 꼬리표의 값을 서로 같게 해주어 같은 집합에 있다고 표시해주는것이다.
이렇게 표시가 되면 이제 다음 간선이 들어왔는데 만약 두 정점이 Find를 통해 찾은 꼬리표의 값이 같다면 둘은 이미 같은 집합에 있는 것이므로 이 간선을 선택해버린다면 사이클이 생긴다는 것이다.
그렇기 때문에 이 간선은 넘어가고 다음으로 작은 간선을 보는것이다.
모든 정점이 연결 되려면 간선의 개수는 정점-1개여야 하므로 위 과정을 간선을 선택할 때마다 수를 누적해 이 수가 정점 -1이 되면 멈추고 가중치를 얻어낸다.
문제해결
> 최대 정점의 수가 1부터 10000개 이므로 꼬리표를 달아줄 parent 배열을 10001개 준다.
> 간선의 연결관계와 가중치를 저장하기 위해 구조체로 두 정점과 가중치를 묶는다.
> 간선들의 관계를 가중치가 작은 것 부터 오름차순 정렬해야 하므로 정렬 기준도 정의해준다.
> 이제 Find와 Union 함수를 정의해준다.
> Find는 들어온 정점에 대해 가장 상위 뿌리가 누구인지 찾아주는 것이다.
parent(f)로 f가 나오면 이 정점은 연결관계가 없다거나 본인이 연결의 축이라는 뜻이다. 근데 f가 안나오면 뭔가 어딘가에 연결이 되었다, 최종 부모가 있다 라는 뜻이다.
이 최종 부모를 재귀로 찾아준다.
> Union은 두 정점의 부모를 찾아서 b 정점의 의 부모를 a 정점과 같게 만들어주는 것이다. 이 처리를 통해 둘은 같은 집합안에 있다 라고 되는것이다.(연결되어있다.)
> 이제 main함수에서 정점의 수를 입력받고 각 정점에 꼬리표를 달아준다.
> 간선의 수 만큼 두 정점과 가중치를 입력받는다.
> 가중치가 작은것부터 오름차순으로 정렬해준다.ㅏ
> 간선의 수 만큼 반복해주며 cnt 즉, 연결된 간선의 수 가 정점-1개면 종료한다.(모두 연결되었다.)
> Find를 통해 간선의 두 정점의 꼬리표를 본다.
둘이 같으면 같은 집합에 있다(연결되어있다)이므로 넘어가고 다르면 둘을 연결해주며 Union연산을 한다.
둘이 연결 됐으므로 가중치를 rst에 추가해주고 cnt도 추가해 준다.다음은 Prim을 사용했다.
Prim은 정점 위주로 따지며 우선순위 큐를 사용한다.
일반 큐를 사용하는 BFS와 달리 우선순위 큐를 사용한다.
기준은 정점의 가중치를 기준으로 한다.
시작으로 어떤 정점의 가중치와 정점을 넣으며
방문처리가 되어있는지 아닌지 확인한다.
되어있지 않으면 연결이 아직 안된 정점이므로 다음 연결할 정점을 탐색한다.
해당 정점과 연결 관계에 있는 정점을 모두 탐색하고 그 정점 까지의 가중치와 정점을 우선순위 큐에 넘긴다.
그러면 우선순위 큐에서 자동으로 가중치 기준으로 정렬이 된다. 다음으로 가장작은 가중치의 정점이 뽑히고 방문처리가 되고, 또 그다음 가중치를 가진 정점이 뽑히고 방문처리가 된다. 이렇게 모든 방문처리가 끝나면(모든 정점이 연결됨) 큐에 남아있는 간선은 따져지지 않고 넘어가며 최종적으로 가중치가 반환된다.
문제해결
> main함수에서 정점, 간선수를 입력받고 이를 저장할 node벡터와 방문처리를 담당할 visited 부울 벡터를 만든다.
> 입력으로 들어온 간선과 가중치를 node벡터에 저장한다.
양 방향 그래프이고 방문처리를 위해 a,b에 대해 모두 저장한다.
> BFS에 가중치 0과 시작정점 1을 넣고 호출한다.
> BFS에선 0,1을 받아 이를 우선순위 큐에 넣고 시작한다.
> while문에서 큐에 top()에 있는 걸 잡고 first를 가중치, second를 정점으로 한다.
> 이를 visited에 넣어 검증하고 방문한적(연결이 안되어있음)이 없으면 탐색을 이어나가며 이 정점까지의 가중치를 누적한다.
> 해당 정점과 관계에 있는 정점을 a로 가져온다.
이 정점의 first는 정점, second는 가중치를나타내므로 이를 뒤집에서 pq의 입력에 맞게 넣어준다.
> 여기서 넣으면 pq내부에서 자동으로 가중치 기준으로 적은 애들 부터 정렬된다.
> 그럼 다음 tw와 tdot에서 알아서 작은애들부터 잡아오고 여기서 작은애들 부터 방문처리가 되므로 while문이 끝나면 제일 적은 비용의 연결이 나온다.코드 - Kruskal
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int V, E;
int parent[10001];
struct node
{
int fdot;
int sdot;
int w;
};
bool cmp(node a, node b)
{
return a.w < b.w;
}
int Find(int f) //뿌리찾기
{
if (parent[f] == f) return f;
return parent[f] = Find(parent[f]);
}
void Union(int a, int b)
{
a = Find(a);
b = Find(b);
if (a != b) parent[b] = a;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> V >> E;
for (int i = 1; i <= V; i++) parent[i] = i;
vector<node> tree;
for (int i = 0; i < E; i++)
{
int a, b, c;
cin >> a >> b >> c;
tree.push_back({ a, b, c });
}
sort(tree.begin(), tree.end(), cmp);
int rst = 0;
int cnt = 0;
for (int i = 0; i < tree.size(); i++)
{
if (cnt == V - 1) break;
if (Find(tree[i].fdot) == Find(tree[i].sdot)) continue;
Union(tree[i].fdot, tree[i].sdot);
rst += tree[i].w;
cnt++;
}
cout << rst << '\n';
}코드 - Prim
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int V, E;
vector<bool> visited;
vector<vector<pair<int, int>>> node;
void BFS(pair<int, int> p)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(p);
int rst = 0;
while (!pq.empty())
{
int tw = pq.top().first;
int tdot = pq.top().second;
pq.pop();
if (visited[tdot]) continue;
visited[tdot] = true;
rst += tw;
for (auto a : node[tdot]) pq.push({ a.second, a.first });
}
cout << rst << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> V >> E;
node.assign(V+1, vector<pair<int, int>>());
visited.assign(V+1, false);
for (int i = 0; i < E; i++)
{
int a, b, c;
cin >> a >> b >> c;
node[a].push_back({ b, c });
node[b].push_back({ a, c });
}
BFS({0, 1});
}
후기
새로운 개념인 MST를 알아 보았다.
Prim과 Kruskal도 처음 알았고 유익했다.
Kruskal의 Find Union의 동작 원리와 필요이유를 이해하는게 좀 복잡했지만 흐름을 따라가보면 Find로 너 그래서 조상이 누군데? 라며 근본적으로 어디 집합에 속한지 찾는것이고, union은 사이클 방지를 위해 방문처리기능을 하는 집합화 시키는 역할이었다.
prime은 의외로 쉬웠는데 우선순위큐의 동작 방식과 사용방식만 알면 기존 Bfs와 같다. 우선순위 큐의 동작 원리가 모호해 처음엔 그냥 정점, 가중치로 넣었더니 결과가 나오길래 넘어갔는데 백준에선 틀려서 다시 공부했다.
가중치를 먼저 넣어 이를 기준으로 정렬이 되어야 맞는 방법이다.
