[백준] 1167 트리의 지름 - Graph Theory / Java

• 문제 링크

1167번: 트리의 지름

 

• 풀이 과정

간선의 정점(node)과 가중치(weight) 정보를 가지는 Edge 클래스를 생성, 인접 리스트에 트리의 정보를 입력받는다.

 

트리의 거리가 가장 먼 두 노드 A, B가 존재할 때,

임의의 노드에서 가장 거리가 먼 노드는 A 또는 B가 된다.

 

따라서 임의의 노드(1) 에서부터 가장 먼 노드를 DFS 탐색을 통하여 구하여 maxNode 에 저장하고,

해당 노드에서부터 가장 거리가 먼 노드까지의 거리가 곧 트리의 지름이 된다.

 

이어서 maxNode를 루트 노드로 DFS 탐색을 통하여 최장 거리(maxDist)를 구하고 이를 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    static List<Edge>[] tree;
    static boolean[] visit;
    static int maxDist = 0;
    static int maxNode;

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

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

        for (int i = 1; i <= v; i++)
            tree[i] = new ArrayList<>();

        for (int i = 0; i < v; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());

            int dest;
            while (!((dest = Integer.parseInt(st.nextToken())) == -1)) {
                int weight = Integer.parseInt(st.nextToken());
                tree[src].add((new Edge(dest, weight)));
            }
        }

        visit = new boolean[v + 1];
        dfs(1, 0);

        visit = new boolean[v + 1];
        dfs(maxNode, 0);

        bw.write(maxDist + "\n");
        bw.flush();
    }

    private static void dfs(int node, int dist) {
        if (dist > maxDist) {
            maxDist = dist;
            maxNode = node;
        }

        visit[node] = true;

        for (Edge dest : tree[node]) {
            if (!visit[dest.node]) {
                dfs(dest.node, dest.weight + dist);
                visit[dest.node] = true;
            }
        }
    }

    private static class Edge {
        int node, weight;

        public Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }

}