백준 1967번 트리의 지름 :: 마이구미

이 글은 백준 알고리즘 1967번 "트리의 지름" 를 풀이한다.

DFS를 통해 문제를 해결할 수 있다.

1967번 - https://www.acmicpc.net/problem/1967

기본 지식이 부족하다면 관련 글을 참고 바란다.

DFS, BFS - http://mygumi.tistory.com/102

Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.

가장 길게 늘어나는 경우인 두 노드를 찾는 것이 문제의 핵심이다.

쉽게 알 수 있는 것은 두 노드는 가장 아래에 있는 노드가 될 것이다.

그렇기에, 가장 깊이 있는 노드를 찾아야하기에 DFS가 적합하게 된다.

가장 깊은 노드 중 가중치가 가장 큰 노드를 찾는다.

찾은 노드를 기준 정점으로 잡고, 다시 한번 가장 가중치가 큰 노드를 찾는다.

2번의 DFS를 통해 문제를 해결할 수 있다.

static int v, u, r;
static ArrayList<Node>[] adj;
static int[] dist;
 
private void solve() {
    adj = (ArrayList<Node>[]) new ArrayList[10001];
    dist = new int[10001];
 
    for (int i = 1; i <= 10000; i++) {
        adj[i] = new ArrayList<>();
    }
 
    int n = sc.nextInt();
 
    for (int i = 0; i < n - 1; i++) {
        int parent = sc.nextInt();
        int child = sc.nextInt();
        int weight = sc.nextInt();
 
        adj[parent].add(new Node(child, weight));
        adj[child].add(new Node(parent, weight));
    }
 
    dfs(1, 0);
 
    r = 0;
    dist = new int[10001];
 
    dfs(u, 0);
    System.out.println(r);
}
 
public static void dfs(int v, int d) {
    dist[v] = d;
 
    if (dist[v] > r) {
        r = dist[v];
        u = v;
    }
 
    for (Node node : adj[v]) {
        int next = node.v;
        int weight = node.w;
 
        if (dist[next] == 0) {
            dfs(next, d + weight);
        }
    }
 
}
 
public class Node {
    int v;
    int w;
 
    Node(int v, int w) {
        this.v = v;
        this.w = w;
    }
}