[C++] 백준 1967 트리의 지름

Guinness·2023년 8월 19일

알고리즘 문제풀이

목록 보기

1/1

백준 1967번 트리의 지름

🧐 문제 분석

어떤 트리가 주어지고, 트리의 간선에는 가중치가 있어 간선의 길이를 의미하게 된다.
임의의 두 노드를 선택해서 두 노드 사이의 간선을 선분으로 만들면, 해당 선분을 지름으로 하는 원을 만들 수 있다. 그리고 이 선분이 최대치가 된다면 트리의 모든 노드가 원 안에 포함되게 된다.

임의의 트리가 주어졌을 때 가장 큰 원을 만들 수 있는 지름의 크기를 구하라.

💡 접근 및 아이디어

어느 정점을 선택하더라도, 해당 정점에서 가장 먼 정점은 트리의 지름의 끝 점임을 알 수 있다.
원 내부에 모든 좌표에 대하여 어떤 좌표로부터 가장 멀리 떨어진 좌표는 원의 가장자리이기 때문이다.
이를 증명하는 과정은 생략하겠다.
그리고 만약 어떤 정점이 원의 가장자리라면, 해당 정점으로부터 가장 멀리 떨어진 정점까지의 선분은 원의 지름을 나타내며 이것이 문제에서 요구하는 트리의 지름이다.

따라서 임의의 정점에서 가장 먼 정점을 구하여 지름의 한쪽 끝 노드를 구하고, 해당 노드로부터 다시 가장 먼 정점을 구한다면 두 정점의 거리가 트리의 지름이 된다.

🧑‍💻 구현

앞선 아이디어로부터 문제를 다음 단계들로 나누어볼 수 있다.

임의의 정점으로부터 거리가 가장 먼 정점(A)을 구한다.
A로부터 거리가 가장 먼 정점(B)을 구한다.
A와 B의 거리가 문제의 정답이다.

임의의 정점을 문제에서 제시한 루트로 하고, (루트 -> A)를 구하는 DFS, (A -> B)를 구하는 DFS 총 2번의 DFS를 통해 A와 B를 확정할 수 있다. 그리고 그 구현 과정에서 자연스럽게 A와 B의 거리를 구할 수 있다.

DFS는 stack과 pair를 이용하여 구현했다. 당연히 재귀를 이용할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

typedef pair<int, int> p;

int n;

bool compare(p a, p b) { // 가장 거리가 먼 정점 정렬용 비교 함수
  return a.first > b.first;
}

p dfs(vector<vector<p> >& link, int start) {
  vector<int> visit(n + 1, 0);
  stack<p> s;
  vector<p> farthest;

  s.push(make_pair(start, 0));
  visit[start] = 1;

  while(!s.empty()) {
    int now = s.top().first;
    int amount = s.top().second;
    s.pop();

    for(p next_p : link[now]) {
      int next = next_p.first, dist = next_p.second;

      if(visit[next] == 0) {
        visit[next] = 1;
        s.push(make_pair(next, amount + dist));
      }
    }

    if(link[now].size() == 1) { // 연결된 정점의 수가 1이라는 것은, 해당 정점이 leaf라는 것을 의미한다. 따라서 현재까지의 거리를 저장한다.
      farthest.push_back(make_pair(amount, now));
    }
  }

  // 저장된 정점을 정렬하여 가장 거리가 먼 정점을 파악한다.
  sort(farthest.begin(), farthest.end(), compare);

  return make_pair(farthest[0].first, farthest[0].second);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int u, v, c;

  cin >> n;

  if(n == 1) {
    cout << 0 << '\n';
    return 0;
  }
  if(n == 2) {
    cin >> u >> v >> c;
    cout << c << '\n';
    return 0;
  }

  // 문제의 접근 및 아이디어 과정에서 Tree의 특성을 이용했지만,
  // 문제의 구현 과정에서 tree의 특성 중 하나인 부모/자식 관계는 의미가 없게 된다.
  // 따라서 정점과 정점의 관계를 연결 여부로만 구현해도 무방하다.
  vector<vector<p> > link(n + 1, vector <p>());

  for(int i = 0; i < n - 1; i++) {
    cin >> u >> v >> c;

    link[u].push_back(make_pair(v, c));
    link[v].push_back(make_pair(u, c));
  }

  // Root(1번 정점)로부터 가장 먼 정점을 구하고,
  p start = dfs(link, 1);

  // 다시 해당 정점으로부터 가장 먼 정점을 구한다.
  cout << dfs(link, start.second).first << '\n';

  return 0;
}

📚 정리 및 소감

해당 문제를 해결하기 위한 증명 과정이 필요했고, 그 과정을 구현하기 위해 하나의 트리 내에서 DFS를 2번 시행하면 된다는 것을 알 수 있었다.

문제의 난이도에 비해서 꽤나 오래 고민했던 문제이다. 필자가 이 문제를 첫 제출한 것은 3년 전이며 고민은 그 이전부터 해 왔었다. 백준에서 이 문제를 마주칠 때마다 왜 나는 해결책을 모를까? 라는 생각을 참 반복했던 것 같다.
그만큼 아이디어를 떠올렸을 때 너무 기뻤고, 그래서 포스팅을 통해 여러분과 해결 과정을 공유해보고 싶었다 ㅎㅎ

그리고 아이디어 상 입력의 조건 요소들 중 의미없는 부분이 있다. 트리의 노드가 1이라는 것과 부모, 자식 노드 순서대로 정점을 제시하는 것은 사실 상 의미 있는 정보가 아니다.
플이 내에서 트리의 특성이 사용되기는 하지만, 루트의 위치가 중요하지 않고, 그렇기 때문에 부모/자식 관계가 의미 없게 된다.
필자는 이러한 정보의 과다 때문에 접근 방법을 떠올리지 못했고, 그동안 여러 시행착오를 겪었기 때문에 이 문제를 해결한 것이 기뻤는지도 모른다...

Guinness