[백준/BOJ/JAVA] 1967 트리의 지름

 

 

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 문제.

( BOJ 1167과 제목까지 똑같은 문제다. 이걸 먼저 푸는게 맞는 듯!! )

 

[백준/BOJ/JAVA] 1167 트리의 지름

1167번 문제와 마찬가지로 특정한 지점에서 가장 먼 정점을 구하고,

그 정점에서 가장 먼 정점을 찾아 거리를 구하면 되는 문제다.

 

그래서 코드는 거의 똑같지만 딱 두 곳이 다르다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class BOJ_1967 {
    static int V, res, leaf;
    static ArrayList<info> list[];
 
    static class info {
        int to;
        int wgt;
 
        public info(int to, int wgt) {
            this.to = to;
            this.wgt = wgt;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        V = Integer.parseInt(br.readLine()); // 정점 개수
        list = new ArrayList[V+1];
 
        for (int i=0; i<=V; i++){
            list[i] = new ArrayList<>();
        }
 
        for (int i=1; i<V; i++) {
            st = new StringTokenizer(br.readLine());
 
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
 
            list[from].add(new info(to, weight));
            list[to].add(new info(from, weight));
        }
 
        // 특정 정점에서 가장 멀리 있는 노드의 지름과 정보 얻기
        dfs(1, 0, 0);
 
        // 리프 노드에서 올라오면서 가장 긴 지름 찾기
        dfs(leaf, 0, 0);
 
        System.out.println(res);
    }
 
    public static void dfs(int node, int parent, int wgt) {
        if (wgt > res) {
            res = wgt;
            leaf = node;
        }
 
        for (int i=0; i<list[node].size(); i++) {
            info next = list[node].get(i);
 
            // 부모 노드는 pass
            if (next.to == parent) continue;
 
            dfs(next.to, node, next.wgt + wgt);
        }
    }
}

 

1) line 28

1167과 다르게 노드의 개수가 1개일 수도 있기 때문에 list[0]도 초기화 시켜줘야 한다.

(1167은 노드(정확히는 정점)의 개수가 2개 이상)

 

2) line 32-41

입력범위는 물론이고, 입력 방식도 달라진다.

입력값에 자식노드들에 대한 정보만 주어졌으나

우리는 leaf에서 다시 타고 올라갈 것이므로 양방향으로 정보를 저장해줘야한다.

 

 

나는.. 첫번째 for문 범위를 놓쳐서 한시간 넘게.. 쳐다보고 있었다..