백준 1167 - 트리의 지름

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

문제 설명

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

 

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

 

문제 풀이

임의의 정점에서 시작해서 가장 먼 정점을 먼저 구한 후, 해당 정점에서부터 가장 먼 거리를 구했을 때, 트리의 성질에 의해 가장 먼 거리가 구해진다. 이를 구현하기 위해 DFS 를 2번 수행해서 임의의 노드 -> 가장 먼 정점을 먼저 구한 후,

해당 노드 -> 가장 먼 정점 을 통해서 답을 구할 수 있었다. 

입력을 받을 때 -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 Node{
		int to;
		int dis;
		public Node(int to, int dis) {
			super();
			this.to = to;
			this.dis = dis;
		}
		@Override
		public String toString() {
			return "Node [to=" + to + ", dis=" + dis + "]";
		}
	}
	static int N,first_max,first_node;
	static List<Node>[] list;
	static boolean[] visited; 
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		list = new List[N+1];
		visited = new boolean[N+1];
		first_max=Integer.MIN_VALUE;
		for(int i=1; i<list.length; i++) {
			list[i] = new ArrayList<Node>();
		}
		for(int i=0; i<N; 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());
				list[from].add(new Node(to, weight));
				list[to].add(new Node(from, weight));
			}
		}
		visited[1]=true;
		DFS(1,0);
		visited = new boolean[N+1];
		visited[first_node]=true;
		DFS(first_node,0);
		System.out.println(first_max);
		
	}
	
	public static void DFS(int start,int sum) {
		if(first_max < sum) {
			first_max = sum;
			first_node = start;
		}
		first_max = Math.max(first_max, sum);
		for(int i=0; i<list[start].size(); i++) {
			if(!visited[list[start].get(i).to]) {
				visited[list[start].get(i).to] = true;
				DFS(list[start].get(i).to, sum+list[start].get(i).dis);
//				visited[list[start].get(i).to] = false;
			}
		}
	}
}