[BOJ_1967] 트리의 지름

설명

---

트리의 각 노드별로 출발해서 어디가 제일 긴 edge 값을 가지는 것인지 판별하는 문제였다. N이 10000이여서 10000*10000 해보니 1억정도라서 아래와 같이 코드를 짜서 모든 노드에서 출발해서 탐색하는 식으로 풀었는데 다른 사람의 풀이를 보니 루트로 부터 한 번 돌리고 루트로 부터 가장 먼 노드를 구해서 탐색하는 식으로 구현하는 방법도 있었다. 

 

사실 탐색 문제의 경우 처음 길을 잘 들여 놓으면 너무 쉬운 문제들이라 크게 설명 할 것이 없다. 초보자라면 차근 차근 재귀의 형태를 실제로 그려보면서 푸는 것도 좋은 방법일듯 하다. 

코드

---

package tree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ_1967 {
    static class Node {
        int node;
        int weight;
        public Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }
    static boolean visited[];
    static List<Node>[] listNode;
    static int ans;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine(), " ");
        int N = Integer.parseInt(tk.nextToken());
        visited = new boolean[N + 1];
        listNode = new ArrayList[N + 1];
        for (int i = 0; i < listNode.length; i++) {
            listNode[i] = new ArrayList<Node>();
        }
        ans = 0;
        for (int i = 0; i < N - 1; i++) {
            tk = new StringTokenizer(in.readLine(), " ");
            int a = Integer.parseInt(tk.nextToken());
            int b = Integer.parseInt(tk.nextToken());
            int d = Integer.parseInt(tk.nextToken());
            listNode[a].add(new Node(b, d));
            listNode[b].add(new Node(a, d));

        }

        for (int i = 1; i <= N; i++) {
            visited = new boolean[N + 1];
            dfs(i,0);
        }
        System.out.println(ans);
    }
    private static void dfs(int idx, int cnt) {
        visited[idx] = true;
        ans = Math.max(cnt, ans);
        for (Node node : listNode[idx]) {
            if (!visited[node.node]) {
                visited[node.node] = true;
                dfs(node.node, cnt + node.weight);
            }
        }
    }
}

1967번: 트리의 지름