문제 개요
오늘의 코딩 테스트 문제는 백준 1197번 '최소 스패닝 트리' 문제다. 그래프의 최소 스패닝 트리를 구현하는 문제로, 알고리즘 기초를 다지는데 적합한 문제다.
문제 분석
주요 포인트:
•
가중치는 음수 가능, 절댓값 100만 이하
•
최소 스패닝 트리의 가중치는 int 범위 내 (음수 가능)
•
정점 개수 V(1 ≤ V ≤ 10,000), 간선 개수 E(1 ≤ E ≤ 100,000)
이 조건들을 고려하며 알고리즘을 설계해야 한다.
접근 방식
그리디 알고리즘을 사용하기로 했다. 최소 가중치를 가진 간선부터 선택해 나가면서, 사이클을 형성하지 않는 간선만 선택하는 방식이다. 크루스칼 알고리즘의 기본 아이디어와 유사하다.
데이터 구조는 다음과 같이 선택했다:
1.
간선 정보: vector<vector<int>>
2.
트리 구조: vector<set<int>>
set을 사용해 각 트리의 정점들을 고유하게 관리하기로 했다.
코드 작성
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
bool comp(const vector<int>& a, const vector<int>& b)
{
if (a[2] < b[2])
return true;
return false;
}
int main()
{
int V, E;
cin >> V >> E;
vector<vector<int>> edges;
for (int i=0; i<E; i++)
{
vector<int> edge(3);
cin >> edge[0] >> edge[1] >> edge[2];
edges.push_back(edge);
}
sort(edges.begin(), edges.end(), comp);
int result = 0;
vector<set<int>> trees;
for (vector<int>& edge: edges)
{
int a = edge[0], b = edge[1], c = edge[2]; // 정점1, 정점2, 간선
int index1 = -1, index2 = -1;
for (int i=0; i<trees.size(); i++)
{
if (trees[i].count(a))
index1 = i;
if (trees[i].count(b))
index2 = i;
}
// 만약 모든 트리에 속해있지 않다면 새롭게 트리를 생성
if (index1 == -1 && index2 == -1)
{
trees.push_back(set<int> {a, b});
}
// 만약 양쪽이 트리에 속하면 같은 트리에 속한다면 제외
else if (index1 == index2)
continue;
// 만약 양쪽이 서로 다른 트리에 속하면 두 트리를 결합
else if (index1 >= 0 && index2 >= 0)
{
for (int element: trees[index2])
trees[index1].insert(element);
trees.erase(trees.begin() + index2);
}
// 만약 한쪽만 트리에 속해있다면 트리에 추가
else if (index1 >= 0 || index2 >= 0)
{
int index = (index1>=0)? index1: index2;
trees[index].insert(a);
trees[index].insert(b);
}
result += c;
}
cout << result << endl;
return 0;
}
C++
복사
주요 로직은 다음과 같다:
1.
간선들을 가중치 기준으로 정렬한다.
2.
정렬된 간선을 순회하며:
•
두 정점이 어떤 트리에도 속하지 않으면 새 트리를 만든다.
•
한 정점만 트리에 속하면 다른 정점을 그 트리에 추가한다.
•
두 정점이 다른 트리에 속하면 두 트리를 합친다.
•
두 정점이 같은 트리에 속하면 그 간선은 무시한다.
문제 해결 및 보완
코드를 작성하고 나서 몇 가지 테스트 케이스로 검증했다. 특별한 문제는 발견되지 않았다.
최적화 관점에서 보면, 현재 구현은 O(E log E)의 시간 복잡도를 가진다. 간선을 정렬하는 데 대부분의 시간이 소요된다. 메모리 사용량은 그래프의 크기에 비례한다.
회고
이 문제를 통해 최소 스패닝 트리 알고리즘을 복습할 수 있었다. 알고리즘 자체는 단순했지만, 각 경우를 분류하고 트리를 정리하는 데 시간이 좀 걸렸다.
솔직히 이 문제가 왜 골드 난이도인지 의문이다. 기본적인 그래프 이론만 알면 쉽게 해결할 수 있는 수준이었다.
