[백준 1167] 트리의 지름

[백준 1167] 트리의 지름

---

접근

트리의 지름

• 트리 내의 두 노드 사이의 가장 긴 경로이다.

문제 풀이

1. 입력을 트리로 변환
   인접 리스트에 Point클래스 (목적지 노드, 가중치) 자료형 사용해서 가중치 있는 그래프 표현.
2. DFS 를 통해서 1에서 가장 멀리 떨어진 노드 탐색
3. 가장 멀리 떨어진 노드를 기준으로 다시 DFS를 진행해서 트리의 지름을 구함.

사용한 알고리즘

DFS

시간 복잡도

O(n)

• 막힌 부분.

1. DFS를 통해서 가장 멀리 떨어진 노드를 탐색하는 것까지는 생각함.
2. 그 이후에 어떻게 지름을 구하는지에 대해서 막혔다.
   지름을 구하기 위해서 다시 DFS 탐색이 필요하다는 것까지 생각을 못했다.. ㅜㅜ
   2-1. 모든 경로의 경우의 수를 탐색해서 지름을 구하는 것도 생각했는데 이때 노드가 많아질수록 모든 경로를 탐색하는데 드는 시간이 매우 커질 것으로 생각이 들어서 포기했다.
3. 트리의 특성을 다시 파악하고 지름을 구하는 방법을 찾아서 적용하였다.

트리의 특성

• 사이클이 없는 구조이다.
  트리 내의 두 노드 사이의 경로는 유일하다.
• 트리의 지름은 이중에서 가장 긴 경로이다.
• 한 정점에서 가장 먼 정점으로 가는 경로와 가장 먼 정점 사이의 경로는 항상 일부가 겹친다. (해당 내용은 아래 이유와 예시를 보면 도움이 된다.)

두번의 DFS로 트리를 구할 수 있는 이유

• A에서 B가 가장 먼 노드라면 A와 B의 거리는 해당 범위의 지름이 된다.
• 각 노드에서 제일 먼 노드까지의 거리를 구해보면 아래 예시와 같다.
• 이때 1에서 5까지가 가장 먼 거리이다. -> 지름
• 임의의 노드에서부터 최장 정점은 1 또는 5를 항상 포함하고 있다.
• 일단 임의의 노드로 시작점을 잡고 해당 노드에서의 가장 먼 노드를 찾고
• 가장 먼 노드를 기점으로 또 가장 먼 노드를 찾게 되어 해당 거리를 갱신하면 해당 트리에서의 지름을 구할 수 있다.

---

전체코드

import java.util.*;
import java.io.*;
public class Main {
    static class Point {
        int destination;
        int weight;

        public Point(int destination, int weight) {
            this.destination = destination;
            this.weight = weight;
        }
    }
    static int V;
    static List<Point>[] list;
    static boolean[] visited;
    static int maxDistance;
    static int farthestNode;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        V = Integer.parseInt(br.readLine());
        StringTokenizer st;
        list = new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) {
            list[i] = new ArrayList<>();
        }
        for (int i = 1; i <= V; i++) {
            st = new StringTokenizer(br.readLine());
            int node = Integer.parseInt(st.nextToken());
            while (true) {
                int destination = Integer.parseInt(st.nextToken());
                if (destination == -1) break;
                int weight = Integer.parseInt(st.nextToken());
                list[node].add(new Point(destination, weight));
            }
        }
        visited = new boolean[V + 1];
        dfs(1, 0);
        System.out.println(maxDistance);
    }
    static void dfs(int node, int distance) {
        visited[node] = true;
        if (distance > maxDistance) {
            maxDistance = distance;
            farthestNode = node;
        }
        for (Point point : list[node]) {
            if (!visited[point.destination]) {
                dfs(point.destination, distance + point.weight);
            }
        }
    }

}