백준 1167: 트리의 지름

문제

풀이

임의의 노드에서 dfs로 가장 먼 노드를 찾아준다.
찾은 노드에서 dfs를 한번 더 진행하면 지름이 구해진다.

코드

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

public class Main {

    static int n,ans,farthest;
    static ArrayList<int[]>[] adj;
    static int[] v;

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n=Integer.parseInt(br.readLine());
        adj=new ArrayList[n+1];
        for(int i=1;i<n+1;i++)adj[i]=new ArrayList<>();

        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());
            while(st.hasMoreTokens()){
                int b=Integer.parseInt(st.nextToken());
                if(b==-1)break;
                int c=Integer.parseInt(st.nextToken());
                adj[a].add(new int[]{b,c});
            }
        }

        ans=0;
        v=new int[n+1];
        farthest=0;
        int node=0;
        for(int i=1;i<n+1;i++){
            if(adj[i].size()!=0){
                node=i;
                break;
            }
        }
        dfs(node,0);
        v=new int[n+1];
        dfs(farthest,0);
        System.out.println(ans);
    }


    static void dfs(int a,int sum){
        v[a]=1;
        if(ans<sum){
            ans=sum;
            farthest=a;
        }
        for(int[] edge:adj[a]){
            if(v[edge[0]]==0)dfs(edge[0],sum+edge[1]);
        }
    }


    /*
5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1
     */
}

#dfs