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

1. 문제 설명

트리의 지름은 트리에서 가장 긴 경로의 길이를 의미합니다. 하나의 트리는 서로 연결된 노드 집합으로, 루트 노드를 기준으로 하여 각 노드가 가지를 이룹니다.
트리의 지름을 구하는 문제는 그래프 이론에서 자주 등장하는 문제로, 주로 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS)을 이용하여 해결됩니다.
이 강좌에서는 트리의 지름을 구하는 방법과 이를 자바스크립트를 사용하여 구현하는 방법을 살펴보겠습니다.

2. 예제 입력 및 출력

입력

        7
        1 2 3
        1 3 4
        2 4 3
        2 5 2
        3 6 1
        3 7 3

출력

7

3. 문제 접근 방법

트리의 지름을 구하는 한 가지 방법은 다음과 같은 두 번의 DFS 또는 BFS를 사용하는 것입니다:

  1. 무작위의 노드에서 시작하여 가장 멀리 떨어진 노드를 찾습니다. 이 노드를 임시 노드라고 하겠습니다.
  2. 임시 노드에서 시작하여 다시 DFS 또는 BFS를 수행하여 가장 멀리 떨어진 노드까지의 거리를 구합니다. 이 거리가 트리의 지름입니다.

4. 자바스크립트 구현

이제 위의 방법을 사용하여 자바스크립트로 트리의 지름을 구하는 코드를 작성해보겠습니다. 시작하기에 앞서, 간단한 데이터 구조를 정의해야 합니다.


    class TreeNode {
        constructor(value) {
            this.value = value;
            this.children = [];
        }
    }

    class Tree {
        constructor() {
            this.root = null;
        }

        addEdge(parentValue, childValue) {
            const parentNode = this.findNode(this.root, parentValue);
            const childNode = new TreeNode(childValue);
            if (parentNode) {
                parentNode.children.push(childNode);
            } else {
                this.root = parentNode; // If root is null, set it as the first node
            }
        }

        findNode(node, value) {
            if (!node) return null;
            if (node.value === value) return node;
            for (const child of node.children) {
                const result = this.findNode(child, value);
                if (result) return result;
            }
            return null;
        }

        diameter() {
            return this.diameterHelper(this.root).diameter;
        }

        diameterHelper(node) {
            if (!node) return { height: 0, diameter: 0 };

            let maxHeight1 = 0, maxHeight2 = 0, diameter = 0;

            for (const child of node.children) {
                const { height, diameter: childDiameter } = this.diameterHelper(child);
                diameter = Math.max(diameter, childDiameter);
                if (height > maxHeight1) {
                    maxHeight2 = maxHeight1;
                    maxHeight1 = height;
                } else if (height > maxHeight2) {
                    maxHeight2 = height;
                }
            }

            diameter = Math.max(diameter, maxHeight1 + maxHeight2);
            return { height: maxHeight1 + 1, diameter };
        }
    }

5. 코드 설명

위 코드는 트리의 지름을 구하는 기능을 포함합니다. 주요 부분을 설명하겠습니다.

  • TreeNode 클래스: 트리의 각 노드를 나타냅니다. 노드 값과 노드의 자식 리스트를 포함합니다.
  • Tree 클래스: 트리를 관리하는 클래스입니다. 자식 노드를 추가하는 addEdge 메서드와 주어진 값을 가진 노드를 찾는 findNode 메서드가 포함되어 있습니다.
  • diameter 메서드: 트리의 지름을 구하기 위해 diameterHelper 함수를 호출합니다.
  • diameterHelper 함수: 재귀적으로 각 노드에서 최대 높이를 계산하고, 현재 노드에서의 지름을 갱신합니다.

6. 성능 분석

이 알고리즘의 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)입니다.
공간 복잡도는 스택 프레임이 최대 트리 높이까지 사용되므로 최악의 경우 O(h), 여기서 h는 트리의 높이를 의미합니다.

7. 결론

자바스크립트를 사용하여 트리의 지름을 구하는 방법을 알아보았습니다. 이와 같은 유형의 문제는 코딩 테스트에서 자주 출제되므로
예제 문제를 많이 풀어보며 익숙해지는 것이 좋습니다.
트리 구조와 DFS/BFS 탐색 방법을 이해하고 활용하는 것이 중요하며, 이러한 기본 개념은 다양한 곳에 응용될 수 있습니다.