백준 1167 - 트리의 지름

문제

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

리뷰

DFS를 활용하여 풀이할 수 있는 문제였다. 트리의 지름을 구하는 로직을
검증하는 과정은 아래 링크를 참고하자.

참고
https://velog.io/@zioo/%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A7%80%EB%A6%84-%EA%B5%AC%ED%95%98%EA%B8%B0

먼저 DFS를 이용하여 한 정점에서 가장 먼 정점을 찾는다.
dfs 메서드는 파라미터로 현재 정점과 현재 정점까지의 비용(w)을
받으며 현재까지 구한 지름(diameter)보다 비용이 먼 경우
가장 먼 노드이므로 diameter 와 farNode를 갱신하며 탐색을 진행한다.

한 번의 DFS를 통해 가장 먼 노드를 구하고 해당 노드에서 다시 DFS를
진행하면 트리의 지름을 도출할 수 있다.

로직의 시간복잡도는 DFS의 $O(V)$으로 수렴하므로 $V=100,000$인 최악의
경우에도 무난히 제한 조건 2초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

public class Main {
    static int radius;
    static int farNode;
    static boolean[] visited;
    static List<List<Node>> graph = new ArrayList<>();

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

        visited = new boolean[V + 1];

        graph.add(null);
        for (int i = 0; i < V; i++)
            graph.add(new ArrayList<>());

        StringTokenizer st;
        int u, v, w;
        while (V-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());

            while ((v = parseInt(st.nextToken())) != -1) {
                w = parseInt(st.nextToken());
                graph.get(u).add(new Node(v, w));
            }
        }

        dfs(1, 0);
        Arrays.fill(visited, false);

        dfs(farNode, 0);
        System.out.println(radius);
        br.close();

    }

    static void dfs(int v, int w) {
        if (radius < w) {
            radius = w;
            farNode = v;
        }

        visited[v] = true;

        for (Node next : graph.get(v)) {
            if (!visited[next.v]) {
                dfs(next.v, w + next.w);
            }
        }
    }


    static class Node {
        int v, w;

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

결과