[자바/백준] 1167_트리의 지름

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

1167번: 트리의 지름

 

정점 사이의 거리와 함께 트리가 입력으로 주어졌을 때,

두 정점 사이의 거리가 가장 긴 거리를 구하는 문제이다.

 

처음엔 DFS로 두 개의 정점을 선택하고,

선택된 두 개의 정점 사이의 거리를 구해 

최종 출력할 변수보다 크면 그 거리를 대입하는 형식으로 풀었다.

 

제대로 값이 구해지긴 하지만

모든 정점의 조합을 구하고 그 값을 구하는 과정이 비효율적이기 때문에 시간 초과가 났다.

 

 

 

정점 사이의 거리가 가장 긴 두 정점(지름)을 구하기 위해서는

DFS나 BFS를 한번 돌려 하나의 정점을 구하고,

또 다시 DFS나 BFS를 돌려 나머지 한 정점을 구할 수 있다고 한다..

(도저히 내 머리로는 생각할 수가 없어서 서치...)

 

이 방법을 통해 코드를 작성했더니 정답처리가 되었다.

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

public class Main {
	private static int V;
	private static List<int[]> list[];
	private static boolean visit[];
	private static int max = -1;
	private static int node;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		V = Integer.parseInt(br.readLine());
		list = new ArrayList[V+1];
		visit = new boolean[V+1];
		
		for(int i=1;i<=V;i++)
			list[i] = new ArrayList<>();
		
		for(int i=1;i<=V;i++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			
			while(true) {
				int v = Integer.parseInt(st.nextToken());
				
				if(v == -1)
					break;
				
				int degree = Integer.parseInt(st.nextToken());
				list[n].add(new int[] {v, degree});
				
			}
		}
		
		DFS(1, 0);
		Arrays.fill(visit, false);
		DFS(node, 0);
		
		System.out.println(max);
	}

	private static void DFS(int idx, int distance) {
		if(max < distance) {
			max = distance;
			node = idx;
		}
		
		visit[idx] = true;
		
		for(int[] a : list[idx]) {
			if(!visit[a[0]]) {
				visit[a[0]] = true;
				DFS(a[0], distance + a[1]);
			}
		}
	}
	
}