1167

[pagh2322]

문제 링크

[pagh2322]

문제 풀이의 핵심 아이디어는 "임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나"에요.

임의로 노드 1를 골라 가장 긴 경로를 구한 뒤, 해당 경로 끝에 있는 노드 x는 트리의 지름에 해당하는 두 끝 노드 중 하나에요.

그렇기에 BFS를 통해 노드 1의 가장 긴 경로를 구한 뒤, 다시 BFS를 통해 노드 x부터 시작해서 가장 긴 경로를 구하면 돼요.

코드

public class Main {

    static ArrayList<Edge>[] arr;
    static int[] distances;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int V = scanner.nextInt();
        arr = new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) arr[i] = new ArrayList<>();
        distances = new int[V + 1];
        visited = new boolean[V + 1];
        for (int i = 0; i < V; i++) {
            int start = scanner.nextInt();
            while (true) {
                int end = scanner.nextInt();
                if (end == -1) break;
                int weight = scanner.nextInt();
                arr[start].add(new Edge(end, weight));
                arr[end].add(new Edge(start, weight));
            }
        }

        bfs(1);
        int max = 1;
        for (int i = 2; i <= V; i++)
            if (distances[max] < distances[i]) max = i;
        distances = new int[V + 1];
        visited = new boolean[V + 1];
        bfs(max);
        Arrays.sort(distances);
        System.out.println(distances[V]);
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (Edge next: arr[curr]) {
                if (visited[next.end]) continue;
                visited[next.end] = true;
                queue.add(next.end);
                distances[next.end] = distances[curr] + next.weight;
            }
        }
    }

}

class Edge {
    int end;
    int weight;

    public Edge(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }
}