백준 1167번(트리의 지름)[JAVA]

풀이

어떤 노드에서 가장 먼 노드는 트리 지름에 해당하는 두 노드 중 하나인 것이 문제 풀이의 핵심이다. 즉, 처음에 임의(이 문제에선 1)의 노드에서 가장 먼 노드를 찾고(트리의 맨 끝을 찾는 다는 말), 그 노드에서 또 가장 먼 노드를 찾으면(트리의 반대쪽 맨 끝을 찾으면), 그 거리가 트리의 지름인 것이다. 각각의 노드들을 class로 관리하는 것도 핵심이다. 이 노드들의 거리는 distance배열로 관리한다.

1. 임의의 노드로 BFS
2. BFS에서 임의의 노드와 다른 노드들 사이의 거리를 distance배열에 저장하고, 여기서 최댓값 가지는 노드를 찾는다.
3. 최댓값 노드를 다시 BFS
4. BFS에서 3번에서 찾은 노드와 다른 노드들 사이의 거리를 distance배열에 저장하고, 이 배열에서 최댓값을 다시 찾는다.

이론 상 처음에 어떠한 노드로 첫 BFS를 해도 통과되어야 하는데, 3이나 4를 넣으면 백준에서 100%까지 갔다가 인덱스 오류가 난다…테스트 케이스가 잘못된 것일까?

소스 코드

import java.util.*;
import java.io.*;

public class 트리의지름 {
	static boolean[] visited;
	static ArrayList<Edge>[] arr;
	static int[] distance;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int v = sc.nextInt();
		
		arr = new ArrayList[v+1];
		for (int i = 1; i < v+1; i++) {
			arr[i] = new ArrayList<Edge>();
		}
		
		for (int i = 0; i < v; i++) {
			int start = sc.nextInt();
			
			while (true) {
				int destination = sc.nextInt();
				if (destination == -1)
					break;
				
				int weight =  sc.nextInt();
				arr[start].add(new Edge(destination, weight));
			}
		}
		
		distance = new int[v+1];
		visited = new boolean[v+1];
		bfs(1);
		int max = 1;
		for (int i = 2; i < v+1; i++) {
			if (distance[max] < distance[i])
				max = i;
		}
		distance = new int[v+1];
		visited = new boolean[v+1];
		bfs(max);
        //배열을 오름차순으로 정렬
		Arrays.sort(distance);
        //오름차순으로 정렬했으니 가장 오른쪽 값(최댓값) 출력
		System.out.println(distance[v]);
	}
	
	static void bfs(int v) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(v);
		visited[v] = true;
		
		while(!q.isEmpty()) {
			int now = q.poll();
			for (Edge i: arr[now]) {
				int e = i.e;
				int value = i.value;
				if (!visited[e]) {
					visited[e] = true;
					q.add(e);
					distance[e] = distance[now] + value;
				}
			}
		}
	}
	
	static class Edge {
		int e;
		int value;
		public Edge(int e, int value) {
			this.e = e;
			this.value = value;
		}
	}
}

태클 감사합니다.
조언 환영입니다.