백준_1167 트리의 지름 (BFS) - 트리의 지름 증명 포함

가장 긴 경로를 찾는 문제이길래, 당연하게 DFS를 사용해모든 경로를 하나하나 고려해봐야겠다고 생각했다.

 

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

public class BJ_1167 {

    static ArrayList<int[]>[] arr;
    static boolean[] visited;
    static int max;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int v, i, e, d;

        v = Integer.parseInt(br.readLine());

        arr = new ArrayList[v+1];
        visited = new boolean[v+1];

        for(i=1; i<v+1; i++) {
            arr[i] = new ArrayList<>();
        }

        for(i=1 ; i<v+1; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            st.nextToken();

            while(true) {
                e = Integer.parseInt(st.nextToken());
                if(e == -1) {
                    break;
                }
                d = Integer.parseInt(st.nextToken());

                arr[i].add(new int[]{e, d});
            }
        }

        max = 0;

        for(i=1; i<v+1; i++) {
            dfs(v, 0);
        }

        System.out.println(new StringBuilder().append(max));
    }

    static void dfs(int v, int d) {
        visited[v] = true;
        if(d>max) {
            max = d;
        }

        for(int[] edge : arr[v]) {
            if(visited[edge[0]] == false) {
                dfs(edge[0], d + edge[1]);
            }
        }

        visited[v] = false;
    }

}

 

테스트 케이스를 입력했을 때 답은 올바르게 나오나 시간초과.

 

계속해서 dfs를 사용하며 어떻게 시간을 줄일지 고민하다가 결국은 풀이를 참고했고

 

그 과정에서

 

"임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나다."

라는 아이디어를 얻긴 했으나, 왜 그런지가 안나와있어 한동안 쓱쓱 그려보다가 아래와 같이 증명해냈다.

 

 

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

public class BJ_1167 {

    static ArrayList<Edge>[] arr;
    static boolean[] visited;
    static int[] distance;

    public static void main(String[] args) throws IOException {

        int v, i, e, value, max;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        v = Integer.parseInt(br.readLine());

        arr = new ArrayList[v+1];
        visited = new boolean[v+1];
        distance = new int[v+1];

        for(i=1; i<v+1; i++) {
            arr[i] = new ArrayList<>();
        }

        for(i=1; i<v+1; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());

            while(true) {
                e = Integer.parseInt(st.nextToken());
                if(e==-1) {
                    break;
                }
                value = Integer.parseInt(st.nextToken());

                arr[s].add(new Edge(e, value));
            }
        }

        bfs(1);
        max = 1; //가장 큰 distance의 인덱스
        for(i=2; i<v+1; i++) {
            if(distance[i] > distance[max]) {
                max = i;
            }
        }
        distance = new int[v+1];
        visited = new boolean[v+1];
        bfs(max);
        Arrays.sort(distance);
        System.out.println(new StringBuilder().append(distance[v]));

    }

    static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        visited[v] = true;

        while(!queue.isEmpty()) {
            int nowNode = queue.poll();
            for(Edge edge : arr[nowNode]) {
                if(visited[edge.e] == false) {
                    visited[edge.e] = true;
                    queue.add(edge.e);
                    distance[edge.e] = distance[nowNode] + edge.value;
                }
            }

        }
    }

    static class Edge {
        int e;
        int value;

        public Edge(int e, int value) {
            this.e = e;
            this.value = value;
        }
    }

}

 

1167번: 트리의 지름