[JAVA] 백준 1167 트리의 지름

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

 

참고 블로그 : https://00ad-8e71-00ff-055d.tistory.com/115

113. Diameter of Tree

 

트리의 지름이란?

트리의 지름은 다음과 같이 정의된다.

• 트리에 존재하는 임의의 정점 u와 v에 대해, 두 정점 사이에는 항상 한 개의 단순 경로가 존재하며 이 단순 경로의 길이를 정점 u와 v 사이의 거리(Distance)라고 한다.
• 트리의 한 정점 u과 임의의 정점 v에 대해, 정점 u와 v 사이의 거리의 최대값을 정점 u에서의 이심률(Eccentricity)이라고 한다.
• 트리의 각 정점에서의 이심률의 최소값을 트리의 반지름(Radius of Tree)이라고 하고 이심률의 최대값을 트리의 지름(Diameter of Tree)이라고 한다.

우리가 구해야 하는건 트리의 지름이다. 트리를 구하는 가장 간단한 방법으로 구현하면 된다. 트리에서 아무 정점을 기준으로 이심률을 구한다. 해당 이심률 대상 정점에서 다시 이심률을 구하면, 그것이 트리의 지름이다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static int edgeNode;
    public static boolean[] visited;
    public static Map<Integer,ArrayList<edge>> vMap;

    public static int max = -1;
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int V = Integer.parseInt(br.readLine());
        
        vMap = new HashMap<>();
        StringTokenizer st;
        for(int i = 0; i < V; i++){
            st = new StringTokenizer(br.readLine());
            int vNum = Integer.parseInt(st.nextToken()); 
            vMap.computeIfAbsent(vNum,k->new ArrayList<edge>());
            int targetVNum = Integer.parseInt(st.nextToken());
            int vCost;
            while(targetVNum !=-1){
                vCost = Integer.parseInt(st.nextToken());
                //vCostArr[vNum][targetVNum] = vCost;
                vMap.get(vNum).add(new edge(targetVNum, vCost));
                targetVNum = Integer.parseInt(st.nextToken());
            }
        }
        visited = new boolean[V+1];
        Arrays.fill(visited,false);
        DFS(1,0);
        visited = new boolean[V+1];
        DFS(edgeNode,0);
        System.out.println(max);
    }
    
    public static void DFS(int node, int cost){
        if(cost > max){
            max = cost;
            edgeNode = node;
        }visited[node] = true;
        ArrayList<edge> ar = vMap.get(node);
        for(int i = 0; i<ar.size(); i++){
            edge destEdge = ar.get(i);
            int destNode = destEdge.targetV;
            if(!visited[destNode]){
                visited[destNode] = true;
                int destCost = destEdge.cost;
                DFS(destNode,cost+destCost);
            }
        }
    }
    static class edge{
        int targetV;
        int cost;
        public edge(int targetV, int cost){
            this.targetV = targetV;
            this.cost = cost;
        }
    }
}