https://www.acmicpc.net/problem/8872
설명이 조금 길지만 정리해보면 포레스트가 주어질 때, 정점들을 잘 이어 트리로 만들면서 트리의 지름이 가장 작게 하면 됩니다. 트리의 지름을 사용하는 문제를 오랜만에 봐서 새로웠습니다.
이 문제를 풀기 위해서는 그리디한 방법을 사용할 수 있습니다. 임의의 트리 두 개를 이을 때, 각 트리의 지름에 중간에 있는 중점끼리 이어주는 것이 새로 만들어지는 트리의 지름을 최소화하는 방법이라는 것을 관찰을 통해 알 수 있습니다. 따라서 트리의 반지름이 가장 큰 트리의 중점에 다른 모든 트리의 중점을 이어주는 것이 최종적으로 만들어지는 트리의 지름을 최소화 하는 방법입니다. 이 경우 트리의 지름이 될 수 있는 경우는 아래의 세 경우입니다.
- 잇기 전에 가장 큰 트리의 지름
- 가장 큰 반지름 + 두번째로 큰 반지름 + $L$
- 두 번째로 큰 반지름 + 세 번째로 큰 반지름 + $L \times 2$
마지막 경우를 떠올리기 어려웠는데, L이 클 경우 2번보다 3번이 커질 수 있습니다.
트리의 지름은 여러 개일 수 있지만 중점은 하나고, 항상 지름 위에 있다는 것의 증명을 옛날에 들었는데 까먹었습니다. 아무튼 그렇기 때문에 트리의 지름을 구하면 트리의 반지름과 중점 역시 구할 수 있습니다. 트리의 지름을 구하는 방법 역시 증명을 들은 거 같은데 까먹었습니다. 아무튼 증명과는 별개로 방법 자체는 크게 어렵지 않기 때문에 해당 방법을 통해서 우선 트리의 지름을 구해줬습니다.
반지름과 중점의 경우 경우 지름을 구한 때 지름의 path를 parent 배열을 통해 기록해 준 뒤, 해당 path 위에서 트리의 반지름이 최소화되는 점을 찾으면 반지름과 중점을 찾을 수 있습니다.
그렇게 구한 반지름들을 vector에 넣어 정렬해준 뒤 답을 구하면 됩니다.
아래는 코드입니다.
#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
#define int long long
#define FF first
#define SS second
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int LINF = 987654321987654321LL;
using namespace std;
int T, n, m, l;
int node, dis;
int visited1[100010], visited2[100010], parent[100010], dist[100010];
vector<int> radius;
vector<vector<pii>> graph;
void dfs1(int x, int sum) {
if (visited1[x]) return;
visited1[x]++;
if (dis < sum) {
dis = sum;
node = x;
}
for (auto [next, cost] : graph[x]) {
if (visited1[next]) continue;
dfs1(next, sum + cost);
}
}
void dfs2(int x, int sum) {
if (visited2[x]) return;
visited2[x]++;
if (dis < sum) {
dis = sum;
node = x;
}
dist[x] = sum;
for (auto [next, cost] : graph[x]) {
if (visited2[next]) continue;
parent[next] = x;
dfs2(next, sum + cost);
}
}
int32_t main(void) {
FastIO;
T = 1;
//cin >> T;
while (T--) {
cin >> n >> m >> l;
graph.resize(n);
memset(parent, -1, sizeof(parent));
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
graph[a].push_back({ b, c });
graph[b].push_back({ a, c });
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (visited1[i]) continue;
node = i;
dis = 0;
dfs1(i, 0);
int s = node;
node = s;
dis = 0;
dfs2(s, 0);
int e = node;
ans = max(ans, dis);
if (s == e) {
radius.push_back(0);
continue;
}
int mn = LINF;
int rad = -1;
int idx = -1;
for (int now = e; parent[now] != -1; now = parent[now]) {
int left = dis - dist[now];
int right = dist[now];
int diff = abs(left - right);
if (mn > diff) {
mn = diff;
rad = max(left, right);
idx = now;
}
}
radius.push_back(rad);
}
sort(rall(radius));
if (radius.size() <= 1) {
cout << ans << endl;
continue;
}
if (radius.size() == 2) {
cout << max(ans, radius[0] + radius[1] + l) << endl;
continue;
}
cout << max({ ans , radius[0] + radius[1] + l, radius[1] + radius[2] + l * 2 }) << endl;
}
return 0;
}
'알고리즘 문제해결 > BOJ' 카테고리의 다른 글
BOJ 2185 직사각형의 합집합 (0) | 2022.08.07 |
---|---|
BOJ 5502 팰린드롬 (0) | 2022.08.04 |
BOJ 5859 Liars and Truth Tellers (0) | 2022.08.02 |
BOJ 1635 1 또는 -1 (0) | 2022.08.01 |
BOJ 16939 2×2×2 큐브 (0) | 2022.07.31 |