728x90
반응형
SMALL
백준 문제 풀이: 1197 [최소 스패닝 트리]
문제 링크: https://www.acmicpc.net/problem/1197
문제 설명:
가중치가 있는 무방향 그래프에서 모든 정점을 연결하는 부분 그래프 중 가중치의 합이 최소가 되는 그래프를 찾는 문제입니다. 이러한 그래프를 "최소 스패닝 트리(MST)"라고 합니다.
문제 해결 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 간선을 저장하는 벡터
vector<pair<int, pair<int, int>>> edges;
int parent[10001]; // 부모 노드 저장 배열
// 부모 노드 찾기 (경로 압축)
int getParent(int n) {
if (parent[n] == n) return n;
return parent[n] = getParent(parent[n]);
}
// 두 노드 연결
void unionParent(int a, int b) {
a = getParent(a);
b = getParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
// 두 노드가 같은 부모를 가지는지 확인
bool findParent(int a, int b) {
return getParent(a) == getParent(b);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int V, E;
cin >> V >> E;
// 초기화: 각 노드의 부모를 자기 자신으로 설정
for (int i = 1; i <= V; i++) {
parent[i] = i;
}
// 간선 정보 입력
for (int i = 0; i < E; i++) {
int a, b, c;
cin >> a >> b >> c;
edges.push_back({c, {a, b}}); // 가중치를 기준으로 정렬
}
// 간선 정렬 (가중치 기준 오름차순)
sort(edges.begin(), edges.end());
int mstWeight = 0; // 최소 스패닝 트리의 총 가중치
// 간선을 하나씩 선택
for (int i = 0; i < edges.size(); i++) {
int weight = edges[i].first;
int u = edges[i].second.first;
int v = edges[i].second.second;
// 두 노드가 같은 집합에 속하지 않으면 연결
if (!findParent(u, v)) {
unionParent(u, v);
mstWeight += weight;
}
}
// 최소 스패닝 트리의 총 가중치 출력
cout << mstWeight << '\n';
return 0;
}
예제 입력:
3 3
1 2 1
2 3 2
1 3 3
예제 출력:
3
코드 설명
- 핵심 알고리즘: 크루스칼 알고리즘을 사용하여 간선의 가중치를 기준으로 정렬한 후, 사이클이 발생하지 않도록 간선을 선택하여 최소 스패닝 트리를 구성합니다.
- 구현 세부사항:
getParent
: 경로 압축을 통해 노드의 부모를 찾습니다.unionParent
: 두 노드를 연결합니다.findParent
: 두 노드가 같은 집합에 속하는지 확인합니다.- 간선을 가중치 기준으로 정렬하고, 사이클이 발생하지 않는 간선만 선택하여 MST를 구성합니다.
- 시간 복잡도:
- 간선 정렬: O(E log E), E는 간선의 개수
- 유니온 파인드: O(α(V)), V는 정점의 개수 (α는 아커만 함수의 역함수로 거의 상수)
- 전체 복잡도: O(E log E)
결과
입력된 그래프에서 최소 스패닝 트리의 총 가중치를 정확히 계산합니다. 크루스칼 알고리즘과 유니온 파인드의 개념을 이해하고 구현하기에 적합한 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!
728x90
반응형
LIST
'BAEKJOON > 그래프' 카테고리의 다른 글
백준 15664번 [N과 M (10)](C++) -yes6686- 티스토리 (0) | 2025.02.05 |
---|---|
백준 17490번 [일감호에 다리 놓기](C++) -yes6686- 티스토리 (0) | 2025.01.27 |
백준 21606번 [아침 산책](C++) -yes6686- 티스토리 (0) | 2025.01.25 |
백준 2887번 [행성 터널](C++) -yes6686- 티스토리 (0) | 2025.01.04 |
백준 2623번 [음악프로그램](C++) -yes6686- 티스토리 (0) | 2025.01.04 |