문제 소개
최소 연결 그래프(minimally connected graph)란 간선을 하나라도 제거하면 그래프가 연결 상태를 잃게 되는 그래프를 의미합니다. 즉, 모든 정점이 서로 연결되어 있으면서 간선이 꼭 필요한 만큼만 존재하는 트리(tree) 형태입니다.
이러한 그래프가 n개의 정점을 가지고 있으며, 간선 정보는 배열 edges에 담겨 주어집니다. 아울러 n개의 정수를 포함하는 배열 vertexValues도 함께 제공됩니다.
규칙
다음 규칙에 따라 점수를 계산합니다.
- 각 정점에 양의 정수를 하나씩 적습니다.
- 간선으로 연결된 두 정점 중 더 작은 값을 해당 간선에 적습니다.
- 모든 간선에 적힌 값을 모두 더한 것이 곧 점수입니다.
목표는 정점에 값을 배치하는 모든 방법 중 점수가 최대가 되는 경우를 찾아, 최대 점수와 그때 각 정점에 적힌 값을 출력하는 것입니다.
예시
n = 6, edges = {{1, 2}, {2, 3}, {2, 4}, {4, 5}, {3, 6}}, vertexValues = {1, 2, 3, 4, 5, 6}가 입력으로 주어졌다고 가정해 보겠습니다. 정점에 값을 3 1 2 4 5 6 순서로 배치하면 최대 점수 15를 얻을 수 있으며, 출력은 다음과 같습니다.
15 3 1 2 4 5 6
접근 방법
이 문제의 핵심은 그리디(greedy) 전략입니다. 간선의 값은 두 끝점 중 작은 값으로 결정되므로, 값이 클수록 간선의 최솟값 역할을 하기 어렵습니다. 따라서 다음과 같이 배치하는 것이 유리합니다.
- 주어진 값을 오름차순으로 정렬합니다.
- 0번 정점을 루트로 삼아 DFS 탐색을 진행하면서, 가장 큰 값부터 탐색 순서대로 정점에 배치합니다.
이렇게 하면 루트에는 최댓값이 놓이고, 자식 정점에는 항상 부모보다 작거나 같은 값이 배치됩니다. 결과적으로 모든 간선의 값은 자식 정점의 값과 같아지므로, 최대 점수는 루트를 제외한 모든 정점 값의 합, 즉 (전체 값의 합 − 최댓값)이 됩니다. 예시에서는 1+2+3+4+5+6 − 6 = 15로 실제 결과와 일치합니다.
알고리즘 단계
위 접근법을 의사 코드로 정리하면 다음과 같습니다.
N := 100
크기가 N인 배열 seq, res 선언
크기가 N인 배열 tp 선언
ans := 0
dfs(p, q) 함수 정의:
res[p] := seq[c]
p가 0이 아니면:
ans := ans + seq[c]
c를 1 감소
tp[p]의 각 원소 x에 대해:
x ≠ q이면:
dfs(x, p)
i := 0부터 i + 1 < n까지 반복:
tmp := edges[i]의 첫 번째 값 - 1
temp := edges[i]의 두 번째 값 - 1
tp[tmp]의 끝에 temp 추가
tp[temp]의 끝에 tmp 추가
i := 0부터 i < n까지 반복:
seq[i] := vertexValues[i]
c := n - 1
seq 배열 정렬
dfs(0, 0) 호출
ans 출력
i := n - 1부터 i >= 0까지 반복:
res[i] 출력
C++ 구현 예제
더 나은 이해를 돕기 위해 다음 구현 예제를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
int seq[N], res[N];
vector<int> tp[N];
int ans = 0, c;
void dfs(int p, int q) {
res[p] = seq[c];
if(p != 0)
ans += seq[c];
c--;
for(auto x : tp[p]) {
if(x != q)
dfs(x, p);
}
}
void solve(int n, vector<pair<int,int>> edges, int vertexValues[]){
for(int i = 0; i + 1 < n; i++) {
int tmp = edges[i].first - 1;
int temp = edges[i].second - 1;
tp[tmp].push_back(temp);
tp[temp].push_back(tmp);
}
for(int i = 0; i < n; i++)
seq[i] = vertexValues[i];
c = n - 1;
sort(seq, seq + n);
dfs(0, 0);
cout << ans << endl;
for(int i = n - 1; i >= 0; i--)
cout << res[i] << " ";
cout << endl;
}
int main() {
int n = 6;
vector<pair<int,int>> edges = {{1, 2}, {2, 3}, {2, 4}, {4, 5},{3, 6}};
int vertexValues[] = {1, 2, 3, 4, 5, 6};
solve(n, edges, vertexValues);
return 0;
}
입력
6, {{1, 2}, {2, 3}, {2, 4}, {4, 5}, {3, 6}}, {1, 2, 3, 4, 5, 6}
출력
15 3 1 2 4 5 6
복잡도 분석
값 정렬에 O(n log n), DFS 탐색에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 인접 리스트와 보조 배열을 사용하기 때문에 공간 복잡도는 O(n)입니다.