[Algorithm] 백준 1167 트리의 지름

문제

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

입력

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

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

출력

첫째 줄에 트리의 지름을 출력한다.

 

---

풀이

1. 임의의 점 A를 선택하고, 그 점을 기준으로 가장 멀리 있는 노드 B를 구한다
2. 노드 B를 기준으로 가장 멀리 있는 노드 C를 구한다
3. 노드 B와 C 사이의 거리가 트리의 지름이다

• 트리는 방향이 있는 그래프가 아니고 싸이클이 없으므로 우선순위큐 등을 사용해서 길이를 업데이트 해주지 않아도 된다
• bfs로 각 점의 인접한 노드를 탐색하며 dist 배열 값에 거리를 저장하여 리턴해준다

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

public class BOJ1167_diameter {

	static class Node{
		int idx, dist;
		
		public Node(int idx, int dist) {
			this.idx = idx; 
			this.dist = dist;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		List<Node>[] list = new ArrayList[n+1];
		for(int i=0; i<=n; i++) list[i] = new ArrayList<>();
		
		for(int i=0; i<n; i++) {
			String[] arr = br.readLine().split(" ");
			int x = Integer.parseInt(arr[0]);
			for(int j=1; j<arr.length-2; j+=2) {
				int y = Integer.parseInt(arr[j]);
				int d = Integer.parseInt(arr[j+1]);
				list[x].add(new Node(y, d));
			}
		}
		
		// 임의의 점 1에서 가장 먼 노드를 찾음 (start)
		int[] dist = bfs(list, 1, n);
		int start = 1;
		for(int i=2; i<=n; i++) 
			if(dist[i]>dist[start]) start = i;
		
		// 가장 테두리에 있는 노드에서 가장 먼 노드와의 거리를 구하면 그것이 트리의 지름
		dist = bfs(list, start, n);
		Arrays.sort(dist);
		System.out.print(dist[n]);
	}
	
	// start로 부터 각 정점의 길이를 구하는 함수
	static int[] bfs(List<Node>[] list, int start, int n) {
		int[] dist = new int[n+1];
		boolean[] visit = new boolean[n+1];
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(start);
		visit[start] = true;
		
		while (!queue.isEmpty()) {
			int k = queue.poll();
			for(Node node : list[k]) {
				if(!visit[node.idx]) {
					visit[node.idx] = true;
					queue.add(node.idx);
					dist[node.idx] = dist[k] + node.dist;
				}
			}
		}
		return dist;
	}
}