[Algorithm] 백준_트리의 지름_1167번 (JAVA)

📝문제

 

💡풀이

예제의 입력을 그림으로 표현하면 아래와 같다.

각 정점에 대해 가장 긴 거리 경로를 구하면

1-3-4-5 :11

2-4-3-1 :9

3-4-5 :9

4-5 :6 

5-4-3-1 :11

 

위 결과의 공통 점은 1또는 5가 경로에 포함 된다는 것이다.

트리의 지름은 1에서 5의 거리인데

 

어떤 정점에서 구해도 1또는 5를 포함해야 가장 긴 경로가 나온다.

 

이러한 결과로 이 문제의 아이디어는 다음과 같이 구할 수 있다.

1. 임의의 정점에서 가장 긴 거리의 정점을 찾는다. 

2. 1에서 찾은 정점을 기준으로 한번 더 가장 긴 거리의 정점을 찾는다.

 

dfs를 두번 호출하여 정답을 구할 수 있다.

 

전체풀이

import java.util.*;
import java.io.*;
class Main{
    static boolean[] visited;
    static int V,diameter;
    static ArrayList<Integer>[] tree;
    static int farthestLen;
    static int farthestV;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        V = Integer.parseInt(br.readLine());
        tree = new ArrayList[V+1];

        for(int i = 0; i <= V; i++){
            tree[i] = new ArrayList<>();
        }
        for(int i = 0; i < V; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());//정점 번호
            int m;
            while((m = Integer.parseInt(st.nextToken())) != -1){
                int distance = Integer.parseInt(st.nextToken());
                tree[n].add(m);
                tree[n].add(distance);
            }
        }

        visited = new boolean[V+1];
        visited[1] = true;
        dfs(1, 0);//1과 가장 먼 정점을 찾는다.

        visited = new boolean[V+1];
        visited[farthestV] = true;
        dfs(farthestV, 0);

        System.out.println(farthestLen);
    }
    public static void dfs(int n, int len){
        if(farthestLen < len){
            farthestV = n;
            farthestLen = len;
        }

        for(int i = 0; i < tree[n].size(); i+=2){
            int v = tree[n].get(i); //연결된 정점
            int d = tree[n].get(i+1); //거리
            if(!visited[v]){
                visited[v] = true;
                dfs(v, len+d);
            }
        }
    }
}

 

🤔Review

처음에 전체를 검색하여 시간초과가 났었는데 
https://moonsbeen.tistory.com/101 이 블로그를 참고하여 이 문제를 이해할 수 있었다🫠 낯설고..어렵다..