자바 코딩테스트 강좌, 트리의 지름 구하기

1. 문제 정의

주어진 트리에서 지름을 구하는 문제는 알고리즘적인 사고를 요구하는 중요한 주제입니다.
트리의 지름은 두 개의 정점 간의 최장 경로의 길이를 말합니다. 이는 트리 구조의 특성을 활용하여 구할 수 있으며, 여러 가지 응용 문제의 기초가 됩니다.
그러므로 이 문제를 해결하는 것은 코딩 테스트에서 괜찮은 성적을 얻기 위한 중요한 단계입니다.

2. 문제 이해하기

트리는 노드로 구성된 비선형 자료구조로서, 레벨과 부모-자식 관계가 존재합니다. 트리의 지름을 구하기 위해서는 트리를 그래프의 일종으로 생각하고
그래프 탐색 알고리즘을 사용해야 합니다.
지름을 구하는 가장 효율적인 방법은 두 번의 깊이 우선 탐색(DFS)을 사용하는 것입니다.

첫 번째 DFS는 임의의 노드에서 시작하여 가장 먼 노드를 찾습니다. 그 다음, 이 새로 찾은 노드에서 다시 DFS를 실행하여 최대 거리를 측정하면
그것이 트리의 지름이 됩니다. 이러한 방식은 O(N)의 시간 복잡도를 가지며, 이는 매우 효율적인 해결책입니다.

3. 문제 해결 전략

문제를 해결하기 위한 전략은 다음과 같습니다.

트리 구성: 먼저 주어진 데이터를 바탕으로 트리 구조를 만듭니다.
DFS 구현: 깊이 우선 탐색 알고리즘을 구현하여 특정 노드에서 가장 먼 노드를 찾습니다.
지름 계산: 첫 번째 DFS에서 찾은 먼 노드에서 다시 DFS를 실행하여 지름을 계산합니다.

4. 자바 코드 구현


import java.util.*;

class TreeNode {
    int val;
    List children;

    TreeNode(int x) {
        val = x;
        children = new ArrayList<>();
    }
}

public class DiameterOfTree {

    private int maxDiameter = 0;

    public int getTreeDiameter(TreeNode root) {
        if (root == null) return 0;
        dfs(root);
        return maxDiameter;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;

        int firstMax = 0; 
        int secondMax = 0;

        for (TreeNode child : node.children) {
            int childDepth = dfs(child);
            if (childDepth > firstMax) {
                secondMax = firstMax;
                firstMax = childDepth;
            } else if (childDepth > secondMax) {
                secondMax = childDepth;
            }
        }

        maxDiameter = Math.max(maxDiameter, firstMax + secondMax);
        return firstMax + 1;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);

        root.children.add(node2);
        root.children.add(node3);
        node2.children.add(node4);
        node2.children.add(node5);

        DiameterOfTree diameter = new DiameterOfTree();
        int result = diameter.getTreeDiameter(root);
        System.out.println("트리의 지름: " + result);
    }
}

위의 코드는 우선 TreeNode 클래스를 정의하고, 각 노드를 연결하는 트리를 만듭니다.
main 메소드는 트리를 설정하고 getTreeDiameter 메소드를 통하여 지름을 계산하도록 되어 있습니다.

5. 코드 설명

이 부분에서는 코드의 주요 부분을 설명하겠습니다.

TreeNode 클래스

TreeNode 클래스는 트리의 각 노드를 나타내며, 노드의 값과 자식 노드 리스트를 포함합니다.
생성자에서 값과 빈 자식 리스트를 초기화합니다.

diameter 변수를 이용한 DFS

DFS는 각 노드를 탐색하면서 자식 노드들의 깊이를 구하고, 최대 깊이를 구합니다.
동시에 최대 지름을 계산할 때, 두 개의 최대 깊이를 사용하여 업데이트합니다.
이 깊이 값은 부모 노드로 돌아갈 때 1을 더해 반환됩니다.

6. 성능 분석

위의 구현은 O(N)의 시간 복잡도를 가지며, 여기서 N은 노드의 수입니다.
각 노드를 한 번씩 방문하므로 매우 효율적입니다.
공간 복잡도 또한 O(H)로, 여기서 H는 트리의 높이에 해당합니다.
이러한 성능은 실제 대규모 데이터에 대해서도 매우 좋은 성능을 보일 것입니다.

7. 다양한 테스트 케이스

다양한 트리 구조를 갖는 테스트 케이스를 통해 알고리즘을 검증할 수 있습니다.
예를 들어, 다음과 같은 트리 구조를 고려할 수 있습니다:

단일 노드 트리
모든 노드가 직렬로 연결된 스패닝 트리
균형 트리
불균형 트리

각 구조에 대해 지름이 올바르게 계산되는지 검증함으로써 알고리즘의 신뢰도를 높일 수 있습니다.

8. 결론

트리의 지름을 구하는 문제는 알고리즘의 기초 개념을 이해하고, DFS를 활용한 효율적인 문제 해결 능력을 강화하는 데 매우 중요한 문제입니다.
제시된 방법을 통해 많은 코딩 테스트 문제를 해결할 수 있는 기반을 마련할 수 있습니다.
자바 언어를 활용한 이 방법론이 여러 상황에 적용될 수 있음을 기억하며, 다양한 문제를 해결하는 데 도움이 되길 바랍니다.