[알고리즘] 1167 트리의 지름

🗒️ 문제 : 백준 1167 트리의 지름

📎 분류 : Tree, Dfs

 

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재한다. 

트리에서 어떤 두 노드를 선택해서 양쪽으로 꽉 당길때 가장 길게 늘어나는 경우, 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

트리의 지름이란, 트리 상에서 가장 먼 거리를 가지는 두 정점 사이의 경로이다. 

트리의 지름은 다음과 같은 순서로 구할 수 있는데,

• dfs를 통해 임의의 정점(x)로부터 가장 먼 정점(y)를 구한다.
• dfs를 통해 구해진 (y)정점으로부터 가장 먼 정점(z)를 구한다.
• (y)정점과 (z)정점을 잇는 경로가 트리의 지름이 된다.

---

증명

dfs를 2번만 진행하면 된다. 아래 블로그에서 증명을 볼 수 있다.

이 방법이 작동하는 이유는

• 트리에서 임의의 노드에서 가장 먼 노드는 항상 지름의 한쪽 끝점이 된다.
• 그 끝점에서 다시 가장 먼 노드를 찾으면, 그것이 지름의 다른 쪽 끝점이 된다.

https://johoonday.tistory.com/217

백준 No.1167 [트리의 지름]

 

코드

package 알고리즘_코딩테스트.dayone.mar01;
import java.util.*;
import java.io.*;

/**
 입력

 5
 1 3 2 -1
 2 4 4 -1
 3 1 2 4 3 -1
 4 2 4 3 3 5 6 -1
 5 4 6 -1
 */
class Node{
    int value;
    int distance;

    public Node(int value,  int distance){
        this.value = value;
        this.distance = distance;
    }
}
public class BOJ_1167 {

    static int result = 0;
    static int farthestNode = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        //노드 개수
        int n = Integer.parseInt(bf.readLine());

        //트리 초기화
        List<Node>[]  tree = new ArrayList[n+1];
        for (int i = 1; i < n+1 ; i++){
            tree[i] = new ArrayList<>();
        }

        // 트리 생성
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            int node = Integer.parseInt(st.nextToken());

            while (true) {
                int connectedNode = Integer.parseInt(st.nextToken());
                if (connectedNode == -1) break;

                int weight = Integer.parseInt(st.nextToken());
                tree[node].add(new Node(connectedNode, weight));
            }
        }

        // 1. 아무 노드(여기서는 1)에서 시작해 가장 먼 노드 찾기
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;
        dfs(tree, visited, 0, 1);

        // 2. 가장 먼 노드에서 다시 시작해 최대 거리 찾기
        visited = new boolean[n + 1];
        visited[farthestNode] = true;
        result = 0; // 결과 초기화
        dfs(tree, visited, 0, farthestNode);

        System.out.println(result);

    }

    private static void dfs(List<Node>[] tree, boolean[] visited, int sum, int start){
        if (sum > result) {
            result = sum;
            farthestNode = start;
        }

        // 시작점에서 인접 노드 탐색
        for (Node node : tree[start]) {
            if (!visited[node.value]) {
                // 방문 체크
                visited[node.value] = true;
                // DFS 수행
                dfs(tree, visited, sum + node.distance, node.value);
            }
        }
    }


}