[백준, Java] 1967번 : 트리의 지름

🔗 문제 링크

https://www.acmicpc.net/problem/1967

😮 문제 해결 방법

Map을 이용해 트리를 만들어 준다.

문제에서 루트노드가 1이라고 주어졌기 때문에 루트 노드를 이용해 가장 멀리 있는 노드를 먼저 탐색한다.

가장 먼 노드를 찾았다면, 해당 노드로 다시 가장 먼 노드를 탐색하면 노드와 노드간 가장 먼 지름이 탐색된다.

1. 루트 노드를 이용해 DFS 탐색 및 가장 먼 노드 찾기
2. 탐색한 가장 먼 노드를 이용해 다시 한번 DFS 탐색 및 지름 갱신

🚩 Java 코드

package com.algorithm.Baekjoon;

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

public class Main_1967_트리의_지름 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Map<Integer, List<Node>> tree = new HashMap<>();

        // 트리 초기화
        for (int node = 0; node <= N; node++) {
            tree.put(node, new ArrayList<>());
        }

        // 트리 연결
        for (int edge = 0; edge < N - 1; edge++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            tree.get(parent).add(new Node(child, weight));
            tree.get(child).add(new Node(parent, weight));
        }

        int rst = getTreeLength(N, tree);
        System.out.println(rst);
        br.close();
    }

    private static int getTreeLength(int size, Map<Integer, List<Node>> tree) {
        startNode = maxStartLength = 0;
        boolean[] visited = new boolean[size + 1];

        // 루트 노드부터 가장 먼 노드 찾기
        getMaxLength(1, visited, tree,  0);

        // 가장 먼 노드로 다시 DFS
        visited = new boolean[size + 1];
        maxStartLength = 0;     // 최장 지름 길이 초기화
        getMaxLength(startNode, visited, tree, 0);
        return maxStartLength;
    }

    private static int startNode, maxStartLength;
    private static void getMaxLength(int node, boolean[] visited, Map<Integer, List<Node>> tree, int weight) {
        visited[node] = true;
        for (Node next : tree.get(node)) {
            if (!visited[next.getNode()]) {
                if (next.getWeight() + weight > maxStartLength) {
                    startNode = next.getNode();
                    maxStartLength = next.getWeight() + weight;
                }
                getMaxLength(next.getNode(), visited, tree, weight + next.getWeight());
            }
        }
    }

    static class Node {
        private int node;
        private int weight;

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

        public int getNode() {
            return node;
        }

        public int getWeight() {
            return weight;
        }
    }
}