[백준] 1967번 트리의 지름

1967번 트리의 지름

---

1. 이해하기

• 트리의 지름은 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.
• 가중치가 있는 간선들로 주어진다.

---

2. 구현하기

• dfs를 이용해 루트로부터 제일 멀리 떨어진 노드 하나를 먼저 찾는다. 그 이후 이 노드로부터 가장 멀리 떨어진 노드를 찾고 그 때의 길이를 구한다.

  void dfs(int here, int cost) {
      visited[here] = true;
      if(ans < cost) {
          ans = cost;
          endPoint = here;
      }
  
      for(int i = 0; i < adj[here].size(); i++) {
          INF there = adj[here][i];
          if(visited[there.next]) continue;
          dfs(there.next,cost+there.cost);
      }
  }

---

3. 전체 코드

#include <iostream>
#include <vector>
using namespace std;
struct INF{
    int next,cost;
};
vector<INF> adj[10001];
bool visited[10001];
int ans,endPoint;
void dfs(int here, int cost) {
    visited[here] = true;
    if(ans < cost) {
        ans = cost;
        endPoint = here;
    }

    for(int i = 0; i < adj[here].size(); i++) {
        INF there = adj[here][i];
        if(visited[there.next]) continue;
        dfs(there.next,cost+there.cost);
    }
}

int main() {
    int N;
    cin >> N;
    for(int i = 0; i < N-1; i++) {
        int from,to,cost;
        cin >> from >> to >> cost;
        adj[from].push_back({to,cost});
        adj[to].push_back({from,cost});
    }
    dfs(1,0);
    ans = 0;
    for(int i = 0; i <= 10000; i++) visited[i] = false;
    dfs(endPoint,0);
    cout << ans << '\n';
    return 0;
}

루트 노트에서 dfs 한번, 여기에서 찾은 노드에서 dfs 다시 한번을 수행해야하기 때문에 인접리스트에 거꾸로도 갈 수 있도록 만들어 준다.