[BaekJoon] 1167 트리의 지름 (Java)

1.  문제 링크

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

2.  문제

요약

• 트리의 지름이란 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말합니다.
• 트리가 입력으로 주어졌을 때, 트리의 지름을 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 100,000보다 작거나 같은 트리의 정점의 개수 V가 주어지고 두 번째 줄부터 V개의 줄에 간선의 정보가 주어집니다. 간선의 정보는 다음과 같이 주어집니다.
  • 먼저 정점 번호가 주어지고, 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리입니다.
  • 각 줄의 마지막에는 -1이 입력으로 주어집니다.
  • 정점 번호는 1부터 V까지 매겨져 있습니다.
  • 주어지는 거리는 모두 10,000보다 작거나 같은 자연수입니다.
• 출력: 첫 번째 줄에 트리의 지름을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    static int V, answer, longestNode;
    static HashMap<Integer, ArrayList<Edge>> map;
    static void input() {
        Reader scanner = new Reader();
        V = scanner.nextInt();
        map = new HashMap<>();
        for(int node = 1; node <= V; node++) {
            int cur = scanner.nextInt();
            map.put(cur, new ArrayList<>());
            while(true) {
                int neighbor = scanner.nextInt();
                if(neighbor == -1) break;
                int weight = scanner.nextInt();
                map.get(cur).add(new Edge(neighbor, weight));
            }
        }
    }

    static void solution() {
        boolean[] visited = new boolean[V + 1];
        answer = 0;
        dfs(1, 0, visited);

        visited = new boolean[V + 1];
        dfs(longestNode, 0, visited);

        System.out.println(answer);
    }

    static void dfs(int node, int weight, boolean[] visited) {
        if(weight > answer) {
            answer = weight;
            longestNode = node;
        }

        visited[node] = true;

        for(Edge e : map.get(node)) {
            if(!visited[e.node])
                dfs(e.node, weight + e.weight, visited);
        }
    }

    static class Edge {
        int node, weight;
        public Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}