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

코드 힌트

1. 문제 이해
   이 코드는 트리에서 가장 긴 경로(지름)를 찾는 문제를 해결합니다.
   • 트리의 지름: 어떤 트리에서 가장 먼 두 노드 사이의 거리입니다.
   • 트리의 지름은 임의의 노드에서 가장 먼 노드를 구하고, 그 노드에서 다시 가장 먼 노드를 찾는 방식으로 구할 수 있습니다.
2. 핵심 아이디어
   • 그래프 표현
     • 노드 수 N만큼의 배열을 생성하고, 각 요소를 List<Node>로 초기화합니다.
     • 인접 리스트(Adjacency List)를 사용해 노드 간의 연결 관계를 효율적으로 관리합니다.
   • 인접 리스트의 관리
     • 2차원 배열로도 연결을 표현할 수 있지만, 인접 리스트를 사용하면 연결된 노드만 관리할 수 있어 효율적입니다.
     • 각 배열의 인덱스에 .add(new Node)로 연결된 노드를 추가합니다.
   • DFS(깊이 우선 탐색) 두 번 수행
     • 첫 번째 DFS: 임의의 노드(예: 1번 노드)에서 가장 먼 노드를 찾습니다.
     • 두 번째 DFS: 첫 번째 DFS로 찾은 가장 먼 노드에서 다시 가장 먼 노드를 탐색합니다. 이때 구한 거리가 트리의 지름입니다.
3. 알고리즘 흐름
   1. 그래프 초기화: 노드 수를 입력받고 인접 리스트를 사용해 그래프를 구성합니다.
   2. 첫 번째 DFS: 1번 노드에서 출발해 가장 먼 노드를 찾습니다.
   3. 두 번째 DFS: 첫 번째 DFS에서 찾은 노드에서 다시 출발해 최대 거리를 구합니다.
   4. 결과 출력: 트리의 지름을 출력합니다.

 

 

import java.util.*;

class Main {

    // 각 노드를 나타내는 클래스 (번호와 비용 저장)
    private static class Node {
        int no;   // 노드 번호
        int cost; // 노드까지의 비용

        Node(int no, int cost) {
            this.no = no;
            this.cost = cost;
        }
    }

    static int n; // 노드의 수
    static List<Node>[] graph; // 그래프 인접 리스트 표현
    static Scanner in; // 입력 스캐너
    static int max = -1; // 최대 거리 저장 변수
    static boolean[] visit; // 방문 여부를 체크하는 배열
    static int furthestNode; // 가장 멀리 있는 노드 번호

    public static void main(String[] args) {
        in = new Scanner(System.in);

        n = in.nextInt(); // 노드의 수 입력
        in.nextLine();

        // 그래프 초기화
        initGraph();

        // 1번 노드에서 가장 먼 노드를 찾음
        visit = new boolean[n + 1]; // 방문 배열 초기화
        dfs(1, 0); // 1번 노드부터 탐색 시작

        // 가장 먼 노드에서 다시 가장 먼 노드까지의 거리를 찾음
        visit = new boolean[n + 1]; // 방문 배열 초기화
        max = -1; // 최대 거리 초기화
        dfs(furthestNode, 0); // 가장 먼 노드에서 탐색 시작

        System.out.println(max); // 최대 거리 출력
    }

    // 깊이 우선 탐색(DFS) - 주어진 노드로부터 거리를 누적하며 탐색
    public static void dfs(int curNode, int sum) {
        visit[curNode] = true; // 현재 노드 방문 처리

        // 누적 거리(sum)가 현재 최대 거리(max)보다 크면 갱신
        if (sum > max) {
            max = sum; // 최대 거리 갱신
            furthestNode = curNode; // 가장 멀리 있는 노드 저장
        }

        // 인접한 노드들을 순회하며 탐색
        for (Node node : graph[curNode]) {
            if (!visit[node.no]) { // 방문하지 않은 노드만 탐색
                dfs(node.no, sum + node.cost); // 재귀 호출로 거리 누적
            }
        }
    }

    // 그래프 초기화
    public static void initGraph() {
        graph = new ArrayList[n + 1]; // 인접 리스트 배열 생성

        // 각 노드에 대해 리스트 초기화
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 그래프에 입력된 간선 정보 추가
        inputGraph();
    }

    // 간선 정보를 입력받아 그래프에 저장
    public static void inputGraph() {
        for (int i = 0; i < n - 1; i++) { // n-1개의 간선 입력 (트리 구조)
            String[] arr = in.nextLine().split(" ");

            int node1 = Integer.parseInt(arr[0]); // 첫 번째 노드
            int node2 = Integer.parseInt(arr[1]); // 두 번째 노드
            int cost = Integer.parseInt(arr[2]);  // 간선 비용

            // 양방향으로 간선 추가
            graph[node1].add(new Node(node2, cost));
            graph[node2].add(new Node(node1, cost));
        }
    }
}