[백준 1967] 트리의 지름(JAVA)

백준 1967번 문제 - 트리의 지름

1967번: 트리의 지름

---

문제 분석 

 

 

• 트리(tree)
  • 사이클이 없는 무방향 그래프이다.
  • 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다.
• 트리의 지름 : 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이
• 트리의 지름을 출력해라.

---

해결 포인트

 

• DFS 사용
  
  • DFS는 최장 값을 반환
• 1부터 N까지 반복하면서 모든 위치에서 시작하는 DFS를 실행

---

코드

 

import java.io.*;
import java.util.*;

public class Main {

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

        int N = Integer.parseInt(br.readLine());

        ArrayList<Edge> [] edges = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) {
            edges[i] = new ArrayList<>();
        }

        for (int i = 0; i < N-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            edges[a].add(new Edge(b,w));
            edges[b].add(new Edge(a,w));
        }

        int result = 0;
        for (int i = 1; i <= N; i++) {
            boolean [] visited = new boolean[N+1];
            result = Math.max(result, DFS(i, visited, edges));
        }

        br.close();

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

    public static int DFS(int n, boolean [] visited, ArrayList<Edge> [] edges) {
        int sum = 0;

        visited[n] = true;
        for(Edge e : edges[n]) {
            if(!visited[e.end]) {
                sum = Math.max(DFS(e.end, visited, edges) + e.w, sum);
            }
        }
        visited[n] = false;

        return sum;
    }

    public static class Edge {
        int end;
        int w;
        public Edge(int end, int w) {
            this.end = end;
            this.w = w;
        }
    }
}