[Algorithm/Java][백준] 1967 트리의 지름

[BOJ] 1967 트리의 지름

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

문제 접근

dfs를 이용해서 접근하였다.
1번 노드에서 dfs를 시작해서 가장 멀리 있는 노드의 인덱스를 저장했다가, 해당 인덱스부터 다시 dfs를 시작해서 그중에 가장 멀리 있는 노드와의 거리를 구하였다.

Code

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

public class BOJ1967 {
    static class Node {
        int end;
        int value;
        Node(int end, int value){
            this.end = end;
            this.value = value;
        }
    }
    static ArrayList<Node>[] tree;
    static boolean[] visited;
    static int n;
    static int max = 0, maxIndex = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        tree  = new ArrayList[n+1];
        for(int i = 0; i<=n; i++){
            tree[i] = new ArrayList<>();
        }

        for(int i = 0; i<n-1; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            tree[from].add(new Node(to,value));
            tree[to].add(new Node(from, value));
        }
        // 1번 노드부터 탐색을 시작하여 가장 멀리 있는 노드를 탐색
        visited = new boolean[n+1];
        visited[1] = true;
        dfs(1,0);

        // 가장 멀리 있는 노드에서부터 탐색
        visited = new boolean[n+1];
        visited[maxIndex] = true;
        dfs(maxIndex,0);

        System.out.println(max);
    }

    /**
     * 재귀 호출을 이용한 dfs 탐색
     * @param i 탐색하는 노드 번호
     * @param score 지금까지 경로의 길이
     */
    public static void dfs(int i, int score){
        // max에 가장 긴 경로의 길이를 저장하고, maxIndex에 해당 노드의 번호 저장
        if(score  > max) {
            max = score;
            maxIndex = i;
        }
        for(Node n : tree[i]){
            if(!visited[n.end]){
                visited[n.end] = true;
                dfs(n.end, score+n.value);
            }
        }

    }
}

어려웠던 점 / 배운 점 / 느낀 점

일단 그래프를 저장할 때 배열로 저장을 하게되면 메모리 초과가 뜬다...
그래프를 표현할 때 행렬로 표현하는 방식이 있는데, 이 문제는 행렬로 표현하게 되면 n*n의 메모리가 들기 때문에 메모리 초과가 뜨는것이다.
그래서 리스트를 이용해서 그래프를 저장했다. 이를 위해서 Node클래스를 만들었고, end(향하는 노드 인덱스)와 value(경로의 길이)를 저장했다.
그리고 처음에는 모든 인덱스에서 dfs를 실행하였는데, 1번 인덱스에서 dfs를 실행하고 거기에서 가장 멀리 있는 노드에 대해서만 다시 dfs를 실행하면 답이 나온다는 것을 알게되었다.(메모리 초과때문에 여러 블로그를 보니까 다 이렇게 풀었다...)
이렇게 하게되면 dfs를 2번밖에 실행하지 않으므로 시간이 2696ms에서 232ms까지 줄어들게 되었다. 역시 골드는 어렵다.