[BOJ]1167 - 트리의 지름 (G2)

문제 링크

1167-트리의 지름

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다.
정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다.
예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다.
각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

문제 풀이

Node 클래스는 도착노드와 간선의 정보를 저장하고 있다.
각 노드별로 인접리스트를 구현해 트리를 저장

그냥 단순히 dfs를 n번 돌리면 시간초과가 날 것 같은데 다른 방법이 생각이 안나서 좀 찾아보다보니 해결방법을 찾았다.

가장 긴 지름을 만드는 노드 node1, node2가 있다고 가정할 때
어떤 한 노드에서 가장 먼 노드는 node1 혹은 node2이다.
가장 먼 노드가 node1이라면, 이에 대한 가장 먼 노드를 구하면 node1과 node2를 모두 구할 수 있다.
참고 : 빈둥벤둥 IT logging - [백준]1167: 트리의 지름 - JAVA

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

class Node {
    int e, cost;

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

public class Main {
    static ArrayList<Node>[] list;
    static boolean[] visited;
    static int node, max;

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

        int n = Integer.parseInt(br.readLine());
        list = new ArrayList[n + 1];

        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            while (true) {
                int to = Integer.parseInt(st.nextToken());
                if(to == -1) break;
                int cost = Integer.parseInt(st.nextToken());

                list[from].add(new Node(to, cost));
            }
        }

        visited = new boolean[n + 1];
        // 임의의 한 점에 대한 것이기 때문에
        // dfs(2,0) dfs(3,0)... 모두 정답
        dfs(1, 0);
        

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


    }

    static void dfs(int x, int len) {
        if (len > max) {
            max = len;
            node = x;
        }

        visited[x] = true;


        for (int i = 0; i < list[x].size(); i++) {
            Node node = list[x].get(i);
            if (!visited[node.e]) {
                dfs(node.e, len + node.cost);
                visited[node.e] = true;
            }
        }
    }


}