문제 개요
오늘의 코딩 테스트 문제는 도시 분할 계획이다. 최소 스패닝 트리(MST) 개념을 활용해 마을을 두 개로 나누는 문제다.
문제 분석
핵심은 다음과 같다:
1.
마을을 두 개로 나눈다.
2.
각 마을 내 모든 집이 연결되어야 한다.
3.
길 유지비의 합을 최소화해야 한다.
결국 MST를 구한 뒤, 가장 비용이 높은 간선 하나를 제거하면 된다.
접근 방식
1.
간선을 비용 기준 오름차순 정렬
2.
유니온-파인드로 사이클 없이 간선 연결
3.
N-1개의 간선을 선택할 때까지 반복
4.
선택된 간선 중 가장 비용이 높은 것을 제거
코드 작성
유니온-파인드 알고리즘을 구현했다. 주요 함수는 다음과 같다:
•
find(int a): 루트 노드 찾기
•
merge(int a, int b): 두 집합 합치기
•
isUnion(int a, int b): 두 노드가 같은 집합인지 확인
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> parent;
bool comp(const vector<int>& a, const vector<int>& b)
{
if (a[2] < b[2])
return true;
return false;
}
// 루트 노드를 찾아서 반환
int find(int a)
{
if (parent[a]==a)
return a;
return find(parent[a]);
}
// 두 유니온 트리를 병합
void merge(int a, int b)
{
a = find(a);
b = find(b);
if (a==b) return;
if (a < b) parent[b] = a;
else parent[a] = b;
}
// 두 노드가 연결되었는지 여부
bool isUnion(int a, int b)
{
return find(a)==find(b);
}
int main()
{
int N, M;
cin >> N >> M;
for (int i = 0; i < N; i++)
parent.push_back(i);
vector<vector<int>> edges;
for (int i = 0; i < M; 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, max_cost = 0;
for (vector<int>& edge: edges)
{
int a = edge[0]-1, b = edge[1]-1, c = edge[2];
if (!isUnion(a, b)) // 연결 되지 않았을 경우
{
merge(a, b);
result += c;
max_cost = max(max_cost, c);
N--;
}
if (N==1)
break;
}
cout << result - max_cost << endl;
return 0;
}
C++
복사
회고
이번 문제로 유니온 파인드를 처음 구현해봤다. 개념은 알고 있었지만 실제 구현은 생각보다 까다로웠다. 특히 find 함수의 경로 압축 최적화 부분이 어려웠다. 더 연습이 필요해 보인다.
크루스칼 알고리즘을 이용한 MST 구성은 이전에 학습한 내용이라 수월했다. 하지만 이를 응용해 두 개의 마을로 나누는 아이디어를 떠올리는 데 약간 시간이 좀 걸렸다.
