백준 1167번 (트리의 지름)

DFS 를 이용해서 문제를 풀지만 트리의 지름을 찾는 알고리즘을 알아야했다.

트리의 지름이란, 트리에서 거리중 가장 긴 것을 말한다.

정점마다 각각의 정점으로 향하는 가중치의 값을 모두 구하기에는 시간제한에 걸릴것 같아

DFS 를 이용하여 임의의점(여기서 나는 1로 두었다) 에서 제일 거리간 긴점,

그 점에서 제일 멀리있는 점이 트리의 지름이라는 글을 읽고 문제를 풀었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

class Node{
	
	public int v, d;
	public Node(int v, int d) {
		this.v = v;
		this.d = d;
	}
}

public class Main {
	
	static int n;
	static List<Node>[] list;
	static boolean[] visit;
	static Node maxDisNode;
	
	
	private static Node dfs(Node node, int dist) {
		
		visit[node.v] = true;
		
		for(Node tmp : list[node.v]) {
			if(!visit[tmp.v])
				dfs(tmp, dist + tmp.d);
		}
		
		if(maxDisNode.d < dist) {
			maxDisNode.d = dist;
			maxDisNode.v = node.v;
		}
		
		return maxDisNode;
	}

	public static void main(String[] args) throws NumberFormatException, IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		list = new ArrayList[n+1];
		visit = new boolean[n+1];
		
		for(int i = 0 ; i <= n ; i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int i = 0 ; i < n ; i++) {
			String[] tmp = br.readLine().split("\\s");
			int a = Integer.parseInt(tmp[0]);
			
			for(int j = 1 ; j < tmp.length ; j += 2) {				
				int b = Integer.parseInt(tmp[j]);
				if( b == -1)
					break;
				
				int c = Integer.parseInt(tmp[j+1]);			
				
				list[a].add(new Node(b, c));
			}			
		}
		
		maxDisNode = new Node(1, 0);
		dfs(maxDisNode, 0);
		
		maxDisNode.d = 0;
		visit = new boolean[n+1];
		
		dfs(maxDisNode, 0);
	
		System.out.print(maxDisNode.d);
	}
}