[BOJ] 1167 - 트리의 지름

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

BOJ - 트리의 지름

문제 유형: 최단 거리, 다익스트라, 트리, 그래프, 트리의 지름

문제 난이도: Gold II

시간 제한: 2초

메모리 제한: 512MB

 

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

 

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

 

출력

첫째 줄에 트리의 지름을 출력한다.

 

풀이

트리의 지름을 구하는 방법은 다음과 같다:

임의의 정점 A에서 가장 멀리 있는 정점 B를 구한다.

정점 B에서 가장 멀리 있는 정점 C를 구한다.

B와 C사이의 거리가 트리의 지름이다.

 

왜 이것이 성립하느냐면, 트리는 특정 점에서 다른 정점으로 가는 경로가 단 하나밖에 없기 때문이다.

즉, 임의의 정점에서 시작해서 가장 멀리 있는 한 점은 트리의 어느 한 끝을 찾은 것이다.

그 한 끝 점에서 가장 멀리 떨어진 정점과의 거리가 바로 트리의 지름이다.

 

이는 가중치의 유무에 상관없이 성립한다.

 

이를 그대로 시행해주면 된다.

최단 거리를 구하는 방법은  자유롭게 구하면 된다. bfs기반의 다익스트라를 써도 괜찮다. 어차피 트리라서 사이클이 없으니 최단거리를 구하는 것은 단순하다.

코드

C++

#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

int v;

pii bfs(int start, vector<vector<pii>> &graph) {
  int farthest = -1;
  int maxDist = -1;
  queue<int> q;
  q.push(start);
  vector<int> dist(v + 1, -1);
  dist[start] = 0;

  while (!q.empty()) {
    int curr = q.front();
    q.pop();

    for (const auto &next : graph[curr]) {
      if (dist[next.first] == -1) {
        dist[next.first] = dist[curr] + next.second;
        q.push(next.first);

        if (dist[next.first] > maxDist) {
          maxDist = dist[next.first];
          farthest = next.first;
        }
      }
    }
  }

  return {farthest, maxDist};
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> v;
  vector<vector<pii>> graph(v + 1);
  for (int i = 0; i < v; ++i) {
    int src;
    int dst, cost;
    cin >> src;

    while (cin >> dst) {
      if (dst == -1)
        break;
      cin >> cost;
      graph[src].push_back({dst, cost});
    }
  }

  auto [endA, _] = bfs(1, graph);

  auto [__, diameter] = bfs(endA, graph);

  cout << diameter << "\n";
  return 0;
}