백준 1167

문제

---

두 노드 N1과 N2가 트리 지름의 정점을 이룬다고 가정

트리를 이루는 임의의 노드 X에서 가장 먼 거리의 노드는 N1 또는 N2

pf) X에서 가장 먼 거리의 노드가 N1도, N2도 아닌, Y라고 하자.

1) X가 N1 또는 N2일 때
--> X와 Y를 잇게 되면 새로운 트리의 지름이 만들어진다. (모순)

2) X가 N1도, N2도 아닐 때
--> N1, N2, X, Y를 잇게 되면 새로운 트리의 지름이 만들어진다. (모순)

따라서 X에서 가장 먼 거리의 노드는 N1 또는 N2이다.

그렇다면 아래의 과정을 거치면 됨.

1) 임의의 노드를 선택한 후 가장 먼 거리(d1)의 노드 N1을 BFS 탐색. 탐색 중 d1 계산

2) N1에서 가장 먼 거리(d2)의 노드 N2를 BFS 탐색 . 탐색 중 d2 계산

계속 거리를 측정하고 갱신해서 가장 먼 거리를 구해야하므로,

탐색하면서 노드 간 거리의 합을 누적할 수 있는 클래스 Node를 만들면 편할 듯

---

Code

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;


public class P1167 {

	static int N; // 트리 노드 개수
	static int result = 0; // 정답
	static int max_node = 0; // 가장 멀리 떨어진 노드 번호
	static ArrayList<ArrayList<Edge>> nodes;
	
	static class Edge { // 간선 정보
		int end; // 정점 노드
		int distance; // 거리
		
		public Edge(int end, int distance) {
			this.end = end;
			this.distance = distance;
		}
	}
	static class Node { // 탐색 용 노드
		int idx;
		int total_distance; // 누적 거리
		
		public Node(int idx, int total_distance) {
			this.idx = idx;
			this.total_distance = total_distance;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		nodes = new ArrayList<>();
		for(int i = 0; i < N; i++) {
			nodes.add(new ArrayList<>());
		}
		
		for(int i = 0; i < N; i++) {
			String[] inputs = br.readLine().split(" ");
			int idx = Integer.parseInt(inputs[0]);
			int j = 1;
			while(true) {
				int v = Integer.parseInt(inputs[j]);
				if(v == -1) {
					break;
				}
				int d = Integer.parseInt(inputs[j + 1]);
				
                // index 주의 --> -1
				nodes.get(idx - 1).add(new Edge(v - 1, d));
				j += 2;
			}
		}
		/*
		for(int i = 0; i < N; i++) {
			for(Edge e : nodes.get(i)) {
				System.out.print(e.end + 1 + " " + e.distance + " ");
			}
			System.out.println();
		}
		*/
		bfs(0);
		bfs(max_node);
		System.out.println(result);
	}
	private static void bfs(int start) {
		boolean[] visited = new boolean[N];
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(start, 0));
		visited[start] = true;
		
		int max_total_distance = 0;
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			
			if(now.total_distance > max_total_distance) {
				max_total_distance = now.total_distance;
				max_node = now.idx;
			}
			
			for(Edge e : nodes.get(now.idx)) {                                                                                             
				if(!visited[e.end]) {
					visited[e.end] = true;
					q.add(new Node(e.end, now.total_distance + e.distance));
 				}
			}
		}
		result = Math.max(result, max_total_distance);
	}

}

---

참고 : https://velog.io/@yanghl98/%EB%B0%B1%EC%A4%80-1167-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A7%80%EB%A6%84-JAVA%EC%9E%90%EB%B0%94