[백준] 1967 1167 트리의 지름

1967 문제보기
1167 문제보기

두 문제는 입력부분만 다르고 사실상 같은문제입니다~!

기본적인 접근법은 이렇습니다.

1. 트리의 지름 양 끝의 노드를 e1, e2라 할 때, 임의의 노트 x에서 가장 먼거리에 놓여진 노드는 반드시 e1 혹은 e2가 된다.
2. e1에서 가장 먼 노드는 e2이고, 그 역도 성립한다.

따라서 아무 노드나 하나 잡고, 가장 먼 노드를 구한 뒤(이게 e1 혹은 e2 둘중에 하나는 알아낼 수 있습니다.)
그 노드에서 가장 먼 노드를 한번 더 구해주면 됩니다! 그럼 그 거리가 반드시 e1과 e2사이의 거리가 되므로 트리의 지름을 구할 수 있습니다.

해당 코드는 1167을 기준으로 작성되었습니다~!

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

class Node{
	int num;
	int dist;
	
	Node(int num, int dist){
		this.num = num;
		this.dist = dist;
	}
}

class Main{
	static int n;
	static int max;
	static ArrayList<Node>[] list;
	
	// i번째 노드에서 가장 먼 곳의 노드의 번호와 거기까지의 거리를 함께 반환하는 함수
	static Node bfs(int i) {
		Queue<Node> q = new LinkedList<Node>();
		q.add(new Node(i, 0)); // 스타트~! 
		boolean[] check = new boolean[n+1]; // 방문여부 체크용 
		check[i] = true;
		
		int maxLen = 0; // 최장거리를 저장 
		int endNode = -1; // 최장거리일때의 노드를 저장 
		
		while(!q.isEmpty()) {
			Node n = q.remove();
			int num = n.num;
			int sumDist = n.dist;
			
			if(maxLen < sumDist) { // 최장거리 갱신 
				maxLen = sumDist;
				endNode = num;
			}
			// 인접 노드를 쭉 돌며 방문 가능하다면 방문해줍니다 
			for(Node node:list[num]) {
				int next = node.num;
				int dist = node.dist;
				if(check[next] == false) {
					check[next] = true;
					q.add(new Node(next, sumDist + dist));
				}
			}
		}
		// 반환
		return new Node(endNode, maxLen);
	}

     public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	n = Integer.parseInt(br.readLine());
    	list = (ArrayList<Node>[]) new ArrayList[n+1];
    	
    	for(int i = 1 ; i <= n ; i++) {
    		list[i] = new ArrayList<>();
    	}
    	
    	for(int i = 0 ; i < n ; i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		int u = Integer.parseInt(st.nextToken());
    		int v = Integer.parseInt(st.nextToken());
    		while(v != -1) {
    			list[u].add(new Node(v, Integer.parseInt(st.nextToken())));
    			v = Integer.parseInt(st.nextToken());
    		}
    	}
    	
		// 임의의 노드로부터 e1혹은 e2를 받아냅니다 
    	Node first = bfs(1);
		// 실제로 지름을 구하는 부분 
    	Node second = bfs(first.num);
    	
    	System.out.println(second.dist);
    	
 
     }
}