백준 1967(트리의 지름)

문제

---

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.

트리의 노드는 1부터 n까지 번호가 매겨져 있다.

---

1167번에서 사용한 코드와 방식을 사용하였다.

루트부터 제일 가중치 값이 먼 노드를 찾고 그 해당 노드에서 제일 가중치 값이 먼 노드를 찾았다.

 

<코드>

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 = 1 ; i < n ; i++) {
			String[] tmp = br.readLine().split("\\s");
			
			int a = Integer.parseInt(tmp[0]);
			int b = Integer.parseInt(tmp[1]);
			int c = Integer.parseInt(tmp[2]);			
			
			list[a].add(new Node(b, c));
			list[b].add(new Node(a, c));
		}
		
		maxDisNode = new Node(1, 0);
		dfs(maxDisNode, 0);
				
		//reset
		maxDisNode.d = 0;
		visit = new boolean[n+1];
		
		dfs(maxDisNode, 0);
		
		System.out.print(maxDisNode.d);
	}
}