BOJ 8872 빌라봉

https://www.acmicpc.net/problem/8872

8872번: 빌라봉

 

설명이 조금 길지만 정리해보면 포레스트가 주어질 때, 정점들을 잘 이어 트리로 만들면서 트리의 지름이 가장 작게 하면 됩니다. 트리의 지름을 사용하는 문제를 오랜만에 봐서 새로웠습니다.

 

이 문제를 풀기 위해서는 그리디한 방법을 사용할 수 있습니다. 임의의 트리 두 개를 이을 때, 각 트리의 지름에 중간에 있는 중점끼리 이어주는 것이 새로 만들어지는 트리의 지름을 최소화하는 방법이라는 것을 관찰을 통해 알 수 있습니다. 따라서 트리의 반지름이 가장 큰 트리의 중점에 다른 모든 트리의 중점을 이어주는 것이 최종적으로 만들어지는 트리의 지름을 최소화 하는 방법입니다. 이 경우 트리의 지름이 될 수 있는 경우는 아래의 세 경우입니다.

 

1. 잇기 전에 가장 큰 트리의 지름
2. 가장 큰 반지름 + 두번째로 큰 반지름 + $L$
3. 두 번째로 큰 반지름 + 세 번째로 큰 반지름 + $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;
}