[백준/Java] 1967 트리의 지름

문제

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

풀이방법

트리의 정의에 따라 한번 갈라지면 다시 만날 수 없음

트리의 지름은 임의의 노드에서 시작해서, 가장 먼 노드의 위치를 찾고

그 노드에서 가장 먼 노드까지의 거리를 찾으면됨

풀이

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

public class Main {
    static int maxDist = 0;
    static int farNode = 0;

    public static void dfs(List<List<int[]>> tree, boolean[] visited, int node, int dist ) {
        visited[node] = true;

        if (dist> maxDist) {
            maxDist = dist;
            farNode = node;
        }

        for (int[] neighbor : tree.get(node)) {
            int nextNode = neighbor[0];
            int weight = neighbor[1];

            if (!visited[nextNode]) {
                dfs(tree, visited, nextNode, dist+weight);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        //[노드번호, 가중치]
        List<List<int[]>> tree = new ArrayList<>();
        for (int i = 0; i<=N; i++) {
            tree.add(new ArrayList<>());
        }
        boolean[] visited = new boolean[N+1];


        for (int i = 0;i<N-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            tree.get(from).add(new int[]{to, weight});
            tree.get(to).add(new int[]{from, weight});
        }

        visited = new boolean[N+1];
        dfs(tree, visited,1,  0);

        visited = new boolean[N+1];
        dfs(tree, visited, farNode, 0);

        System.out.println(maxDist);
    }
}