백준 트리의 지름

문제

내가 생각했을때 문제에서 원하는부분

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다.
둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다.
간선에 대한 정보는 세 개의 정수로 이루어져 있다.
첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고,
두 번째 정수는 자식 노드를,
세 번째 정수는 간선의 가중치를 나타낸다.
간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고,
부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다.
루트 노드의 번호는 항상 1이라고 가정하며,
간선의 가중치는 100보다 크지 않은 양의 정수이다.

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

내가 이 문제를 보고 생각해본 부분

Edge 클래스: 그래프의 간선을 표현하는 클래스. 각 간선은 연결된 노드와 가중치를 포함한다.
graph 배열: 인접 리스트로 트리를 표현하기 위해 List<Edge>[] 형태로 선언한다.
각 인덱스는 노드 번호에 해당하며,
해당 노드와 연결된 간선들을 저장한다.
BufferedReader를 사용하여 입력받는다.
첫 번째 줄에서 노드의 개수 n을 읽어온다.
다음 n-1줄에서 각 간선의 정보를 읽어와 부모 노드,
자식 노드,
가중치를 그래프에 추가한다.
이때 무방향 그래프이므로 양쪽 모두에 간선을 추가한다.
첫 번째 다익스트라 호출:
루트 노드(1번 노드)에서 시작하여 가장 먼 노드를 찾는다.
이 노드는 트리의 한 끝점이 된다.
두 번째 다익스트라 호출:
첫 번째 호출에서 찾은 가장 먼 노드에서 다시 다익스트라를 수행하여 최대 거리를 계산한다.
이 최대 거리가 트리의 지름이 된다.
dijkstra 메소드는 주어진 시작 노드에서 모든 노드까지의 최단 경로를 계산한다.
PriorityQueue를 사용하여 현재 최단 거리를 가진 노드를 우선적으로 처리한다.
각 노드에 대해 방문한 적이 없는 경우 새롭게 계산된 거리를 업데이트하고,
우선순위 큐에 추가한다.
모든 노드를 탐색한 후 가장 먼 노드와 그 거리를 반환한다.
최종적으로 계산된 트리의 지름을 출력한다.
그래프 초기화 및 입력 받기 -> 첫 번째 다익스트라 호출하여 가장 먼 노드 찾기 -> 두 번째 다익스트라 호출하여 지름 계산 -> 결과 출력

코드로 구현

package baekjoon.baekjoon_24;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 백준 1967번 문제
public class Main832 {
    static class Edge {
        int node;
        int weight;

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

    static List<Edge>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

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

        for(int i = 0; i < n - 1; i++) {
            String[] input = br.readLine().split(" ");
            int parent = Integer.parseInt(input[0]);
            int child = Integer.parseInt(input[1]);
            int weight = Integer.parseInt(input[2]);

            graph[parent].add(new Edge(child, weight));
            graph[child].add(new Edge(parent, weight)); // 무방향 그래프
        }

        // 첫 번째 다익스트라
        int farthestNode = dijkstra(1)[0];

        // 두 번째 다익스트라
        int diameter = dijkstra(farthestNode)[1];

        System.out.println(diameter);
        br.close();
    }

    static int[] dijkstra(int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        int[] distances = new int[graph.length];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[start] = 0;
        pq.add(new Edge(start, 0));

        int farthestNode = start;
        int maxDistance = 0;

        while(!pq.isEmpty()) {
            Edge current = pq.poll();
            int currentNode = current.node;

            for(Edge edge : graph[currentNode]) {
                int newDistance = distances[currentNode] + edge.weight;
                if(newDistance < distances[edge.node]) {
                    distances[edge.node] = newDistance;
                    pq.add(new Edge(edge.node, newDistance));
                }
            }
        }

        // 가장 먼 노드와 그 거리를 찾기
        for(int i = 1; i < distances.length; i++) {
            if(distances[i] > maxDistance) {
                maxDistance = distances[i];
                farthestNode = i;
            }
        }

        return new int[]{farthestNode, maxDistance};
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.