[Baekjoon 20924] 트리의 기둥과 가지 - JAVA

[Gold IV] 트리의 기둥과 가지 - 20924

문제 링크

성능 요약

메모리: 127284 KB, 시간: 1504 ms

분류

깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리

제출 일자

2024년 9월 29일 13:01:51

문제 설명

시청 공무원 마이크로는 과장으로부터 시에 있는 나무의 기둥의 길이와 가장 긴 가지의 길이를 파악하라는 업무 지시를 받았다.

마이크로는 ICPC Sinchon Winter Algorithm Camp에서 배운 트리 자료 구조를 이용하면 이 작업을 좀 더 수월하게 할 수 있으리라 판단했다.

마이크로는 트리의 기둥과 가지를 분류하기 위해 기가 노드를 추가로 정의하였다.

기가 노드는 루트 노드에서 순회를 시작했을 때, 처음으로 자식 노드가 $2$ 개 이상인 노드다. 기둥-가지를 줄여 기가 노드라 이름 붙였다. 위 그림에서 기가 노드는 $4$번 노드다.

단, 위 그림과 같이 리프 노드가 단 $1$개인 경우 리프 노드가 동시에 기가 노드가 된다.

또한, 위 그림과 같이 루트 노드가 동시에 기가 노드인 경우도 가능하다.

)

• 트리의 기둥은 루트 노드에서부터 기가 노드까지다. 위 그림에서 기둥은 $1-2-3-4$ 이다.
  기둥의 길이는 기둥의 간선 길이의 합인 $1 + 2 + 3 = 6$ 이 된다.
• 트리의 가지는 기가 노드에서부터 임의의 리프 노드까지다. 위 그림에서 가지는 $4-5-6-7$, $4-5-8$, $4-9$, $4-10-11$, $4-10-12$ 총 $5$개가 있다.
  가지의 길이는 가지의 간선 길이의 합이다. 다행히도 가장 긴 가지의 길이 하나만 기재하면 된다. $4-10-12$ 가지가 간선 길이의 합 $3 + 3 = 6$ 으로 가장 긴 가지이다.

마이크로는 시의 나무를 트리 자료 구조로 옮겼다. 그런데 과장이 마이크로에게 또 다른 업무를 지시했다! 너무 바쁜 마이크로를 대신해 트리의 기둥과 가장 긴 가지의 길이를 측정하자.

입력

첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다.

이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 노드와 $b$번 노드가 연결되어있으며 이 간선의 길이가 $d$($1 \le d \le 1\,000$)임을 의미한다. 노드는 $1$번부터 $N$번까지 정수 번호가 매겨져 있으며 같은 간선은 여러 번 주어지지 않는다.

트리가 아닌 그래프는 입력으로 주어지지 않는다.

출력

나무의 기둥의 길이와 가장 긴 가지의 길이를 출력한다.

문제 풀이

해당 문제는 트리에서 루트 노드로부터 지가 노드까지의 경로(기둥)와 지가 노드에서 가장 긴 가지의 길이를 찾아야 한다.

트리는 각 노드간의 연결 정보를 이용해 구성되어있다.

(때문에, 인접 리스트를 사용하여 구성했다.)

기둥을 찾기 위해서 루트 노드에서 시작해 연결된 노드로 이동하면서 해당 노드가 지가 노드인지 판단한다.

(지가 노드란 자식 노드가 2개 이상인 노드를 말하며, 루트 노드 자체가 지가 노드일 수도 있다.)

지가 노드를 만날 때까지 이동하면서 각 간선의 길이를 누적합하여 기둥의 길이를 계산한다.

가장 긴 가지 찾기 위해서 지가 노드에서 출발해 DFS를 사용해 각 리프 노드까지의 거리를 계산했다.

각 경로의 길이를 비교해 가장 긴 경로의 길이를 구하면 그 값이 문제에서 요구하는 답이 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    private static boolean[] visited;
    private static int totalNodes, rootNode, gigaNode;
    private static ArrayList<ArrayList<Node>> adjacencyList;

    public static void main(String[] args) throws IOException {
        initializeGraph(); // 그래프 초기화 및 입력 처리
        System.out.println(getPillar(rootNode) + " " + getMaxBranchLength(gigaNode));
    }

    // 그래프 초기화 및 입력 받기
    private static void initializeGraph() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
        totalNodes = Integer.parseInt(st.nextToken());
        rootNode = Integer.parseInt(st.nextToken());

        adjacencyList = new ArrayList<>(totalNodes + 5);
        visited = new boolean[totalNodes + 5];
        for (int i = 0; i < totalNodes + 5; i++) {
            adjacencyList.add(new ArrayList<Node>());
        }

        for (int i = 1; i < totalNodes; i++) {
            st = new StringTokenizer(bufferedReader.readLine());
            int fromNode = Integer.parseInt(st.nextToken());
            int toNode = Integer.parseInt(st.nextToken());
            int distance = Integer.parseInt(st.nextToken());

            adjacencyList.get(fromNode).add(new Node(toNode, distance));
            adjacencyList.get(toNode).add(new Node(fromNode, distance));
        }
    }

    //지가 노드 찾기 및 지가 경로 길이 계산
    private static int getPillar(int currentNode) {
        visited[currentNode] = true;
        gigaNode = currentNode;
        if (isGigaNode(currentNode)) {
            return 0;
        }
        Node nextNode = findNextNode(currentNode);
        return getPillar(nextNode.targetNode) + nextNode.weight;
    }

    //다음 노드 찾기
    private static Node findNextNode(int currentNode) {
        Node nextNode = adjacencyList.get(currentNode).get(0);
        return visited[nextNode.targetNode] ? adjacencyList.get(currentNode).get(1) : nextNode;
    }

    // 지가 노드 조건 검사
    private static boolean isGigaNode(int currentNode) {
        return (currentNode == rootNode && adjacencyList.get(currentNode).size() > 1) ||
                totalNodes == 1 ||
                adjacencyList.get(currentNode).size() > 2 ||
                (currentNode != rootNode && adjacencyList.get(currentNode).size() == 1);
    }

    // 지가 노드에서 최대 가지 길이 계산
    private static int getMaxBranchLength(int currentNode) {
        visited[currentNode] = true;
        int maxBranchLength = 0;
        for (Node adjacentNode : adjacencyList.get(currentNode)) {
            if (visited[adjacentNode.targetNode]) continue;
            maxBranchLength = Math.max(maxBranchLength, getMaxBranchLength(adjacentNode.targetNode) + adjacentNode.weight);
        }
        return maxBranchLength;
    }

    // 내부 클래스: 노드 표현
    private static class Node {
        private int targetNode, weight;

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