[백준] 1167 트리의 지름

문제 출처: www.acmicpc.net/problem/1167

1167번: 트리의 지름

: 트리의 지름은 트리에서 임의의 두 점 사이의 거리 중 가장 긴 거리를 말한다.

: 처음에는 dfs로 모든 지점을 시작점으로하여 가장 긴 거리를 찾도록 했다.

: 하지만 이렇게 했을 경우 트리의 정점의 개수가 최대 100,000개가 될 수 있기 때문에 시간 초과가 나게 된다.

: 따라서 트리의 지름을 구하는 수학적인 방법을 알아야 할 필요가 있다.

: 사실 트리의 지름을 구하기 위해서는 한 지점에서 가장 먼 지점을 찾고, 또 다시 그 지점에서 가장 먼 지점의 길이를 찾으면 된다.

: 따라서 처음 시작점으로 지정할 루트노드를 0번으로 만들어 1번을 연결시켜놓고(가중치는 0) 가장 먼 노드를 찾는다.

: 그 후 그 노드에서 부터 가장 먼 노드까지의 길이를 찾으면 답이 된다.

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

public class 트리의지름_1167 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N;
	static ArrayList<Edge>[] map;
	static boolean[] v;
	static class Edge{
		int v, w;

		public Edge(int v, int w) {
			super();
			this.v = v;
			this.w = w;
		}

		@Override
		public String toString() {
			return "Edge [v=" + v + ", w=" + w + "]";
		}
		
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		N = Integer.parseInt(br.readLine());
		map = new ArrayList[N+1];
		v = new boolean[N+1];
		for(int i = 0; i < N+1; i++) {
			map[i] = new ArrayList<>();
		}
		map[0].add(new Edge(1, 0));
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int cur = Integer.parseInt(st.nextToken());
			
			while(true) {
				int vertex = Integer.parseInt(st.nextToken());
				if(vertex == -1) break;
				
				int weight = Integer.parseInt(st.nextToken());
				map[cur].add(new Edge(vertex, weight));
			}
		}

		dfs(0, 0);
		max = Integer.MIN_VALUE;
		v = new boolean[N+1];
		dfs(maxNode, 0);
		System.out.println(max);
	}
	static int maxNode = -1;
	static int max = Integer.MIN_VALUE;
	private static void dfs(int cur, int sum) {
		v[cur] = true;
		for(int i = 0, size = map[cur].size(); i < size; i++ ) {
			int next = map[cur].get(i).v;
			if(!v[next]) dfs(next, sum+map[cur].get(i).w);
		}
		if(sum > max) {
			max = sum;
			maxNode = cur;
		}
		
	}
	
}