[Java] BOJ 1167번 트리의 지름

[Java] BOJ 1167번 트리의 지름

풀이

우선 임의의 점(1번 정점)에서 가장 긴 거리를 갖고 있는 정점을 구하고 해당 정점에서 다시 긴 거리를 구하면 그 거리가 최대 거리가 되므로 정답을 구할 수 있습니다.

코드

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Main { public static class Edge { int v, weight; public Edge(int v, int weight) { this.v = v; this.weight = weight; } } public static int V, answer, maxVertex; public static boolean[] visited; public static List[] edgeList; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; V = Integer.parseInt(br.readLine()); edgeList = new ArrayList[V + 1]; for (int i = 1; i <= V; ++i) { edgeList[i] = new ArrayList<>(); } for (int i = 1; i <= V; ++i) { st = new StringTokenizer(br.readLine(), " "); int from = Integer.parseInt(st.nextToken()); while (true) { int to = Integer.parseInt(st.nextToken()); if (to == -1) { break; } int weight = Integer.parseInt(st.nextToken()); edgeList[from].add(new Edge(to, weight)); } } visited = new boolean[V + 1]; go(1, 0); visited = new boolean[V + 1]; go(maxVertex, 0); System.out.println(answer); } public static void go(int v, int w) { if (answer < w) { answer = w; maxVertex = v; } visited[v] = true; for (Edge edge : edgeList[v]) { if (!visited[edge.v]) { go(edge.v, edge.weight + w); } } } }

from http://comgong-man.tistory.com/247 by ccl(A) rewrite - 2021-10-21 17:27:13