트리의 지름 (백준 1167번)

 

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

 

결론

임의의 정점에서 가장 거리가 긴 노드를 찾는다. (dfs 한 번)
찾아진 노드에서 가장 거리가 긴 노드까지의 거리를 구하면 된다. (dfs한 번)
(총 dfs 두 번에 트리의 지름을 찾을 수 있다)

 

 

설명

위 트리의 경우 1 - 3 - 4 - 5 가 트리의 지름(트리에서 임의의 두 점 사이의 거리 중 가장 긴 것) 경로가 된다.

 

여기서 트리의 지름이 되는 양 끝 노드는 1과 5이다.

 

이 때 임의의 정점에서 거리가 가장 긴 노드는 1 혹은 5를 반드시 지나게 된다.

 

1에서 거리가 가장 긴 경로 : 1 - 3 - 4 - 5

2에서 거리가 가장 긴 경로 : 2 - 4 - 5

3에서 거리가 가장 긴 경로 : 3 - 4 - 5

4에서 거리가 가장 긴 경로 : 4 - 5

5에서 거리가 가장 긴 경로 : 5 - 4 - 3 - 1

 

 

따라서 임의의 정점에서 dfs를 수행하여 거리가 가장 긴 노드를 구하면, 트리의 지름이 되는 한 노드를 알수 있다.

트리의 지름이 되는 한 노드에서 dfs를 수행하여 거리가 가장 긴 경로를 구하면 트리의 지름을 구할 수 있다!

 

코드

package com.mincheolsong;
import java.io.*;
import java.util.*;

public class Main {

    // boj 1167 트리의 지름
    // 트리에서 임의의 두 점 사이의 거리 중 가장 긴 길이를 구하라.

    static int V;
    static List<Node>[] adj;
    static boolean[] visited;
    static int longest_v, longest_e;
    
    static void solve(int v,int w){

        if(w > longest_e){
            longest_v = v;
            longest_e = w;
        }

        for(Node node : adj[v]){
            if(visited[node.idx]) continue;
            visited[node.idx]=true;
            solve(node.idx,w+node.w);
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        V = Integer.parseInt(br.readLine());
        adj = new ArrayList[V+1];
        for(int i=1;i<=V;i++){
            adj[i] = new ArrayList<>();
        }

        for(int i=0;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 w = Integer.parseInt(st.nextToken());
                adj[from].add(new Node(to,w));
            }
        }

        // 임의의 하나의 정점 (1) 에서 가장 먼 정점 찾기
        visited = new boolean[V+1];
        longest_e = 0;
        longest_v = 0; // 가장 먼 정점 찾아짐
        visited[1]=true;
        solve(1,0);

        visited = new boolean[V+1]; // 방문배열 초기화
        visited[longest_v]=true; // 가장 먼 정점 방문처리
        longest_e = 0; // 가장 먼 간선 길이 초기화
        solve(longest_v,0);

        System.out.println(longest_e);

    }

}

class Node{
    int idx, w;

    public Node(int idx, int w){
        this.idx = idx;
        this.w = w;
    }

}