트리. 트리의 지름

문제

• 트리의 지름은 트리의 두 노드 사이의 거리중 가장 긴 거리를 지름으로하는 길이다.
  그 지름을 구하는 문제이다.

해결방향성

• 트리의 양쪽끝을 쭉 늘리면 하나의 원의 지름이된다.
• 트리의 지름을 구하기 위해서는 DFS를 두번 사용하면된다.
  DFS의 조건으로 가장 긴 길이를 max에 저장하는 방식으로 트리의 지름을 가지는 끝노드를 찾은후
  다시 끝노드를 시작으로 DFS를 돌리면, 가장 긴 길이, 즉, 트리의 지름을 알수있다.

코드

import java.io.*;
import java.util.*;

// 이진트리 일단 아닌걸로 가정

class Vertex{
    int num;
    int weight;

    public Vertex(int num, int weight) {
        this.num = num;
        this.weight = weight;
    }
}

public class Main {
    static int N;
    static ArrayList<ArrayList<Vertex>> graph;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        graph = new ArrayList<>();

        graph.add(new ArrayList<>());
        for (int i = 0; i < N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < N - 1; i++) { // 간선 입력받음
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            graph.get(start).add(new Vertex(end, weight));
            graph.get(end).add(new Vertex(start, weight));
        }
        // 그래프 연결 끝. 노드 N개

        visited = new boolean[N + 1];
        // 끝점 찾기?
        DFS(1, 0);
        Arrays.fill(visited, false);
        DFS(maxNode, 0);

        bw.write(String.valueOf(max));

        bw.flush();
        br.close();
        bw.close();
    }

    static boolean[] visited;
    static int max = 0;
    static int maxNode = 1;
    private static void DFS(int start, int weight) {
        if (max < weight) {
            max = weight;
            maxNode = start;
        }

        visited[start] = true;

        for (Vertex endVertex : graph.get(start)) {
            int j = endVertex.num;
            int distance = endVertex.weight;

            if (!visited[j]) {
                visited[j] = true;
                DFS(j, distance + weight);
            }
        }
    }



}

결론

• 노드의 수가 N개이기때문에 결국 N개의 노드를 가진 무방향 그래프가 생성된다.
• 이를 바탕으로 DFS를 돌리면되는데, BFS를 자주 쓰던 나에겐 다시한번 DFS를 상기시켜주는 좋은 문제였다. DFS : 깊이 우선 탐색으로, 조건을 weight > max를 주면 최장 길이에 속하는 루트가 저장이 된다.
• 이 루트의 끝점은 지름의 끝점에 무조건 속하므로, DFS를 2번 돌리는 것으로 다익스트라를 여러번 돌리는 것을 대신할수있다.