[BOJ] 1967. 트리의 지름

인접리스트의 DFS로 풀수있었던 문제이다.

리프노드에서 리프노드까지 가는 가장 긴경우를 지름이라 할 수 있는데 그것을 찾는 문제였다. 맨처음엔 가장 긴 간선을 기준으로 찾아보는 방법을 시도했는데, 가장 긴 간선이 꼭 포함되라는 보장이 없으므로 틀린방법으로 접근하였었다. 도움을 받아 풀었는데 다음과 같은 방법으로 풀었다. 1.루트에서 가장 멀리있는 리프노드의 인덱스를 찾고, 2. 그 리프노드에서 가장 멀리떨어진 리프노드의 거리가 지름. 이와 같은 방법으로 해결하였고, DFS를 이용하여 모든 경우를 다보았다.

package boj3;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_1967_트리의지름 {
    
    
    static int N;
    static List<Node>[] tree;
    
    static boolean[] visit;
    static int distance;
    static int index;
    
    static class Node{
        int point,weight;
        Node(int p,int w){
            point=p;weight=w;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        N=Integer.parseInt(br.readLine());
        tree=new ArrayList[N+1];
        for(int i=1;i<=N;i++)
            tree[i]=new ArrayList<>();
        
        for(int i=0;i<N-1;i++) {
            st=new StringTokenizer(br.readLine());
            int u=Integer.parseInt(st.nextToken());
            int v=Integer.parseInt(st.nextToken());
            int w=Integer.parseInt(st.nextToken());
            
            tree[u].add(new Node(v, w));
            tree[v].add(new Node(u, w));
        }
        
        distance=0;
        index=0;
        visit=new boolean[N+1];
        dfs(1,0);
        
        
        distance=0;
        visit=new boolean[N+1];
        dfs(index,0);
        System.out.println(distance);
    }
    
    static void dfs(int cur, int sum) {
        visit[cur]=true;
        if(distance<sum) {
            distance=sum;
            index=cur;
        }
        
        for(Node n : tree[cur]) {
            int next=n.point;
            int weight=n.weight;
            
            if(visit[next]==false) {
                dfs(next,sum+weight);
            }
        }
        
    }
    
}