[백준/BOJ/JAVA] 1167 트리의 지름

 

 

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

트리의 지름을 구하는 문제!!

 

5                   // 트리의 정점의 개수 V
1 3 2 -1            // 정점 번호, 연결된 정점 번호, 연결된 정점까지의 거리, 끝(-1)
2 4 4 -1
3 1 2 4 3 -1        // 연결된 정점이 2개
4 2 4 3 3 5 6 -1    // 연결된 정점이 3개
5 4 6 -1

입력값은 위와 같다.

 

list에 트리 연결 정보를 저장하고, 부모를 제외한 연결 노드들을 타고 들어가며 거리를 재면 된다.

이 때, 대체 어느 노드에서 시작해야 가장 긴 거리를 찾을 수 있을지가 문제인데..

모든 노드들에서 다 탐색할 필요 없이 임의의 시작점에서 가장 먼 노드 하나를 구하고,

거기서 다시 가장 먼 노드를 찾으면 된다.

 

참고 블로그

[백준] 1167 : 트리의 지름 (JAVA/자바)

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class BOJ_1167 {
    static int V, res, leaf;
    static ArrayList<info> list[];
 
    static class info {
        int to;
        int wgt;
 
        public info(int to, int wgt) {
            this.to = to;
            this.wgt = wgt;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        V = Integer.parseInt(br.readLine()); // 정점 개수
        list = new ArrayList[V+1];
 
        for (int i=1; i<=V; i++){
            list[i] = new ArrayList<>();
        }
 
        for (int i=1; i<=V; i++) {
            st = new StringTokenizer(br.readLine());
 
            int from = Integer.parseInt(st.nextToken());
            while (true) {
                int to = Integer.parseInt(st.nextToken());
                if (to == -1)
                    break;
                int weight = Integer.parseInt(st.nextToken());
                list[from].add(new info(to, weight));
            }
        }
 
        // 특정 정점에서 가장 멀리 있는 노드의 지름과 정보 얻기
        dfs(1, 0, 0);
 
        // 리프 노드에서 올라오면서 가장 긴 지름 찾기
        dfs(leaf, 0, 0);
 
        System.out.println(res);
    }
 
    public static void dfs(int node, int parent, int wgt) {
        if (wgt > res) {
            res = wgt;
            leaf = node;
        }
 
        for (int i=0; i<list[node].size(); i++) {
            info next = list[node].get(i);
 
            // 부모 노드는 pass
            if (next.to == parent) continue;
 
            dfs(next.to, node, next.wgt + wgt);
        }
    }
}