백준 1967: 트리의 지름

문제

풀이

• 처음 풀이
  모든 노드에서 dfs를 시작해 가장 긴 거리를 찾았다.

• 개선된 풀이

  1. 아무 노드를 잡아서 dfs를 진행해 가장 먼 노드를 찾아준다.
  2. 찾은 노드에서 dfs를 시작해 가장 먼 거리를 찾아주면 정답이다.

코드

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

public class Main {

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

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

        n=Integer.parseInt(br.readLine());
        edges=new ArrayList[n+1];
        for(int i=0;i<n+1;i++)edges[i]=new ArrayList<>();
        v=new int[n+1];
        ans=0;
        farthest=0;
        for(int i=0;i<n-1;i++){
            st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());
            int c=Integer.parseInt(st.nextToken());
            edges[a].add(new int[]{b,c});
            edges[b].add(new int[]{a,c});
        }
//        for(int i=1;i<n+1;i++){
//            dfs(i,0);
//        }
        // 수정된 부분
        dfs(1,0);
        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 i=0;i<edges[a].size();i++){
            int[] tmp=edges[a].get(i);
            if(v[tmp[0]]==1)continue;
            dfs(tmp[0],sum+tmp[1]);
        }
        v[a]=0;
    }
}

#dfs