백준 1167 (트리의 지름) - java

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

 

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

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

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

 

유형 : 트리

 

접근 방식

 

트리의 지름

• 트리 상에서 가장 먼 거리를 가지는 두 정점 사이의 거리

• 위의 예시에서 가장 긴 트리의 지름은 dis(9,12)이다.
• 트리의 지름에는 가장 중요한 한가지 특징이 있다.
  • 트리의 지름은 2개의 리프 노드 사이의 거리이다 !!!!!!

트리의 가중치가 양수라고 가정한다면 만약 거리에서 1 정점이라도 리프 노드가 아니라면 해당 값에서 리프 노드까지의 가중치를 더하면 최댓값이 갱신되기 때문이다 !

• 트리의 지름 구하는 방법
  • 시작 노드에서 가장 먼 거리의 노드(y)를 구한다.
  • 노드(y)에서 가장 먼 거리의 노드(z)를 구한다.
  • y와 z를 잇는 경로가 트리의 지름이 된다.

시작 노드

시작 노드는 아무 노드나 잡아도 된다.

 

전체 코드

import java.util.*;
import java.io.*;
public class Main {
    static int n = 0;

    static int result = 0;
    static int end = 0;

    static boolean[] v;

    static ArrayList<Node>[] graph;
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(bf.readLine(), " ");
            int idx = Integer.parseInt(st.nextToken());

            while(true){
                int v = Integer.parseInt(st.nextToken());

                if(v == -1)
                    break;

                int c =  Integer.parseInt(st.nextToken());

                graph[idx].add(new Node(v,c));
            }
        }

        v = new boolean[n+1];
        dfs(1,0);

        v = new boolean[n+1];
        dfs(end,0);

        System.out.println(result);
        bf.close();
    }

    static void dfs(int cur,int dis){

        v[cur] = true;

        if(result < dis){
            result = dis;
            end = cur;
        }

        for(Node next : graph[cur]){

            if(!v[next.v]){
                dfs(next.v,dis + next.c);
            }
        }

    }
}
class Node{
    int v;
    int c;

    Node(int v,int c){
        this.v = v;
        this.c = c;
    }
}