[백준] 1167: 트리의 지름

문제

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

---

코드

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

public class bj_1167 {

    private static boolean[] visited;
    private static ArrayList<ArrayList<Node>> tree = new ArrayList<>();
    private static int max = 0;
    private static int start;

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

        int V = Integer.parseInt(br.readLine());
        for (int i = 0; i < V + 1; i++) {
            tree.add(new ArrayList<>());
        }

        for (int i = 0; i < V; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            while (true) {
                int e = Integer.parseInt(st.nextToken());
                if (e == -1) {
                    break;
                }
                int cost = Integer.parseInt(st.nextToken());
                tree.get(from).add(new Node(e, cost));
            }
        }

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

        visited = new boolean[V + 1];
        max = 0;
        dfs(start, 0);

        System.out.println(max);
    }

    private static void dfs(int v, int dist) {
        if (dist > max) {
            max = dist;
            start = v;
        }

        visited[v] = true;

        for (Node node : tree.get(v)) {
            if (!visited[node.e]) {
                dfs(node.e, node.cost + dist);
            }
        }
    }


    private static class Node {
        private final int e;
        private final int cost;

        public Node(int e, int cost) {
            this.e = e;
            this.cost = cost;
        }
    }

}

---

풀이

트리는 모든 정점이 사이클 없이 연결된 그래프이며, 한 정점에서 다른 정점으로 가는 경로는 유일하다. 따라서 트리의 지름을 구하는 방법은 다음과 같다.

1. 임의의 정점에서 가장 멀리 떨어진 정점을 찾는다.
2. 해당 정점에서 다시 가장 멀리 떨어진 정점까지의 거리를 측정하면, 그 값이 트리의 지름이 된다.

이 부분은 이 블로그에서 설명을 잘해주셨으니 참고하면 될 것 같다.

 

 

첫 번째 DFS: 가장 먼 노드 찾기

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

• 아무 노드(1번 정점)에서 DFS를 수행하여 가장 먼 노드를 찾는다.
• 이때 가장 먼 노드를 `start`에 찾는다.

 

두 번째 DFS: 트리의 지름 찾기

visited = new boolean[V + 1];
max = 0;
dfs(start, 0);
System.out.println(max);

• 첫 번째 DFS에서 찾은 `start` 노드에서 다시 DFS를 수행한다.
• 이번에는 가장 먼 거리(max)를 구하면 그것이 트리의 지름이 된다.

 

DFS 함수

private static void dfs(int v, int dist) {
    if (dist > max) {
        max = dist;
        start = v;
    }

    visited[v] = true;

    for (Node node : tree.get(v)) {
        if (!visited[node.e]) {
            dfs(node.e, node.cost + dist);
        }
    }
}

1. 현재 정점 `v`까지의 거리가 `max`보다 크다면, `max`와 `start`를 갱신한다.
2. 방문한 노드를 체크한다. (`visited[v] = true`)
3. 현재 정점과 연결된 모든 노드 중 방문하지 않은 노드로 DFS를 수행한다.

 

 

 

처음 문제를 봤을 때는 너무 어려워서... 이리저리 찾아봤었는데 다 풀고 나니깐 쉽다... 물론 일주일 후에 다시 보면 색다르긴 하겠지만...