[백준] 1167번 : 트리의 지름

1167번: 트리의 지름

[DFS]

트리의 지름을 구하기 위해선, 1번 정점을 Root 정점으로 두고, 1번에서 DFS를 시작한다. 그 후 1번에서 가장 먼 정점 v1을 기록하고, v1에서 DFS를 해서 가중치의 합이 가장 큰 것을 반환하도록 한다.

 

처음에는, 입력을 받을 때 각 인접리스트의 사이즈가 가장 작은 것들을 배열이나 리스트에 담아서, 그 곳에 담긴 정점에서 DFS를 하며 가중치의 합이 가장 큰 곳을 찾아보았으나, 정점이 최대 10만개이기도 하고, 말단노드(간선이 1개인) 정점이 굉장히 많을 수 있어 시간초과를 받았다.

 

    static void DFS(int start, int sum, int dist){

        visit[start] = true;
        sum += dist;

        for(Edge e : list[start])
            if(!visit[e.tg])
                DFS(e.tg, sum, e.d);


        if(max < sum){
            maxVertex = start;
            max = sum;
        }
    }

# Code </>

public class Main {

    static class Edge{
        int tg, d;
        public Edge(int target, int dist){
            tg=target; d=dist;
        }
    }
    static final int N = 100001;
    static boolean[] visit;
    static List<Edge>[] list = new ArrayList[N];
    static int max, maxVertex;

    static void DFS(int start, int sum, int dist){

        visit[start] = true;
        sum += dist;

        for(Edge e : list[start])
            if(!visit[e.tg])
                DFS(e.tg, sum, e.d);

        if(max < sum){
            maxVertex = start;
            max = sum;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int v = Integer.parseInt(br.readLine());

        for(int i=1; i<=v; i++)
            list[i] = new ArrayList<>();

        for(int i=0; i<v; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int home = Integer.parseInt(st.nextToken());

            while(true){
                int target = Integer.parseInt(st.nextToken());
                if(target == -1) break;
                int dist = Integer.parseInt(st.nextToken());

                list[home].add(new Edge(target, dist));
            }
        }

        visit = new boolean[N];
        max = 0;
        maxVertex = 0;
        DFS(1, 0, 0);

        visit = new boolean[N];
        max = 0;
        DFS(maxVertex, 0, 0);

        System.out.println(max);
    }
}