https://www.acmicpc.net/problem/1647
[필자 사고]
문제에서 주어진 조건은 최소 경로를 이용하여 마을을 2개 만드는 방법이다.
필자는 크루스칼 알고리즘이 떠올랐다.
가중치들을 오름차순으로 정렬한 뒤 작은것부터 마을을 연결하다 보면 최소 스패닝 트리가 만들어진다.
ㅇㅣ 방식을 이용하여 마지막 하나의 연결만 하지 않고 가중치가 최소로 된 마을 2개가 만들어진다.
이미 같은 마을을 확인한느 방법은 유니온 파인드 알고리즘을 적용 했다.
[코드 해설]
- 구조체와 정렬
- Node 구조체를 정의하여 간선의 시작 노드, 끝 노드, 가중치를 저장합니다.
- cmp 함수는 간선의 가중치를 기준으로 오름차순 정렬을 위한 비교 함수입니다.
- 입력 처리 (Input 함수)
- 노드 개수 N과 간선 개수 M을 입력받습니다.
- parent 벡터는 각 노드의 부모를 나타내며, 초기에는 모든 노드가 자기 자신을 부모로 가집니다.
- 모든 간선 정보를 읽어와 arr 벡터에 저장합니다.
- Union-Find
- find 함수는 주어진 노드의 루트 부모를 찾고, 경로 압축을 통해 최적화를 수행합니다.
- isSame 함수는 두 노드가 같은 집합에 속해 있는지 확인합니다.
- Union 함수는 두 노드를 같은 집합으로 합칩니다.
- 최소 스패닝 트리 (MST) 생성 (Game_Start 함수)
- 간선을 가중치 오름차순으로 정렬합니다.
- 정렬된 간선을 순회하며, 두 노드가 같은 집합에 속하지 않은 경우에만 간선을 MST에 추가합니다.
- 이를 위해 Union을 호출하고, 추가된 간선의 인덱스를 arrIdx에 저장합니다.
- MST를 완성한 뒤, 마지막 간선을 제외한 나머지 간선의 가중치를 합산하여 ans에 저장합니다.
- 마지막 간선은 제외되므로 MST의 두 번째로 큰 가중치를 기준으로 답을 구합니다.
- 결과 출력
- 최종적으로 계산된 ans 값을 출력합니다.
[소스 코드]
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Node {
int start;
int end;
int weight;
};
bool cmp(Node a, Node b) {
return a.weight < b.weight;
}
int N, M;
int ans=0;
vector<int> parent;
vector<Node> arr;
vector<int> arrIdx;
int find(int a) {
if (a == parent[a])return a;
return parent[a] = find(parent[a]);
}
bool isSame(int a, int b) {
a = find(a);
b = find(b);
if (a == b)return true;
return false;
}
void Union(int a, int b) {
a = find(a);
b = find(b);
if (a != b)parent[b] = a;
}
void Input() {
cin >> N >> M;
parent.resize(N + 1);
for (int i = 0; i <= N; i++) {
parent[i] = i;
}
for (int i = 0; i < M; i++) {
int start, end, weight;
cin >> start >> end >> weight;
arr.push_back({ start,end,weight });
}
}
void Game_Start() {
sort(arr.begin(), arr.end(), cmp);
for (int i = 0; i <arr.size(); i++) {
int start = arr[i].start;
int end = arr[i].end;
int weight = arr[i].weight;
if (isSame(start, end) == false) {
Union(start, end);
arrIdx.push_back(i);
}
}
for (int i = 0; i < arrIdx.size()-1; i++) {
int idx = arrIdx[i];
int weight = arr[idx].weight;
ans += weight;
}
}
int main(void) {
Input();
Game_Start();
cout << ans;
}