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

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다.

트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다.

먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다)

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다.

예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다.

각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

문제해결방법

임의의 정점에서 가장 멀리 있는 정점을 찾고 그 정점에서 가장 먼 정점까지의 거리가 트리의 지름이다.

근데 나는 위의 개념을 몰라서 다른 방식으로 풀었다.

1번 정점을 루트 노드로 가정하고 DFS를 돌면서 각 리프노드까지의 거리와

각 정점에서 자식 노드들이 리프노드 까지 갔을때의 거리 중 1, 2번째로 먼 두 거리를 더한 값들을 비교해서 가장 먼 거리를 트리의 지름으로 계산하였다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main1167_트리의지름 {
    
    public static int n, radius = 0;
    public static boolean[] visited;
    public static ArrayList<int[]>[] tree;
    
    public static int travel(int v) {
        int max = 0;
        int[] arr = new int[tree[v].size()];
        for(int i=0; i<tree[v].size(); i++) {
            int[] node = tree[v].get(i);
            if(!visited[node[0]]) {
                visited[node[0]] = true;
                int d = node[1] + travel(node[0]);
                arr[i] = d;
                if(max < d) max = d;
            }
        }
        if(tree[v].size()>1) {
            Arrays.sort(arr);
            int temp = arr[arr.length-1] + arr[arr.length-2];
            if(radius < temp) radius = temp;
        }
        if(radius < max) radius = max;
        return max;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        tree = new ArrayList[n+1];
        visited = new boolean[n+1];
        for(int i=1; i<tree.length; i++) {
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            tree[num] = new ArrayList<int[]>();
            while(true) {
                int v = Integer.parseInt(st.nextToken());
                if(v==-1) break;
                int d = Integer.parseInt(st.nextToken());
                tree[num].add(new int[] {v, d});
            }
        }
        visited[1] = true;
        travel(1);
        System.out.println(radius);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.