C# 코딩테스트 강좌, 트리의 지름 구하기

안녕하세요, 여러분! 오늘은 C#을 활용하여 트리의 지름을 구하는 문제를 다뤄보도록 하겠습니다. 본 글에서는 문제 정의, 알고리즘 설계, 구현과 테스트 과정을 통해 이해를 돕겠습니다.

문제 정의

트리의 지름은 트리의 두 노드 사이에 있는 가장 긴 경로의 길이를 의미합니다. 주어진 트리의 정점의 개수 n과 n-1개의 엣지를 통해 트리가 표현됩니다.
이를 바탕으로, 트리의 지름을 구하는 함수를 작성하세요.

입력

n : 정점의 수 (2 ≤ n ≤ 10^5)
트리를 구성하는 n-1 개의 엣지. 각 엣지는 u v w 형태로 주어지며, u와 v는 연결된 정점, w는 두 정점 간의 가중치입니다.

출력

트리의 지름을 나타내는 정수 값.

알고리즘 설계

트리의 지름을 구하는 가장 일반적인 방법은 “두 번의 깊이 우선 탐색(DFS)”을 사용하는 것입니다.
아래에 간단한 절차를 정리하겠습니다.

임의의 정점에서 DFS를 실행하여 가장 먼 정점 A를 찾습니다.
정점 A에서 다시 DFS를 실행하여 가장 먼 정점 B를 찾고, 그 거리를 계산합니다.

이 방법을 통해 트리의 지름을 효율적으로 구할 수 있습니다. 최악의 경우 시간 복잡도는 O(n)입니다.

C# 코드 구현

다음은 위의 알고리즘을 기반으로 한 C# 코드입니다:

using System;
using System.Collections.Generic;

class TreeDiameter
{
    static List>[] graph;
    static bool[] visited;
    static int maxDistance;
    static int furthestNode;

    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        graph = new List>[n + 1];

        for (int i = 1; i <= n; i++)
        {
            graph[i] = new List>();
        }

        for (int i = 0; i < n - 1; i++)
        {
            var edge = Console.ReadLine().Split();
            int u = int.Parse(edge[0]);
            int v = int.Parse(edge[1]);
            int w = int.Parse(edge[2]);
            graph[u].Add(new Tuple(v, w));
            graph[v].Add(new Tuple(u, w));
        }

        // 첫 번째 DFS로 가장 먼 정점 찾기
        visited = new bool[n + 1];
        maxDistance = 0;
        DFS(1, 0);

        // 두 번째 DFS로 지름 구하기
        visited = new bool[n + 1];
        maxDistance = 0;
        DFS(furthestNode, 0);
        
        // 결과 출력
        Console.WriteLine(maxDistance);
    }

    static void DFS(int node, int distance)
    {
        visited[node] = true;

        if (distance > maxDistance)
        {
            maxDistance = distance;
            furthestNode = node;
        }

        foreach (var neighbor in graph[node])
        {
            if (!visited[neighbor.Item1])
            {
                DFS(neighbor.Item1, distance + neighbor.Item2);
            }
        }
    }
}

코드 설명

1. graph: 인접 리스트 형식으로 트리의 엣지를 저장하기 위한 배열입니다.
2. visited: DFS 진행 중 방문한 정점을 추적하기 위한 배열입니다.
3. maxDistance: 현재까지 발견한 가장 긴 경로의 길이를 저장합니다.
4. furthestNode: 가장 먼 정점의 ID를 저장합니다.
5. Main(): 트리 구조를 입력받고, 두 번의 DFS를 호출하여 트리의 지름을 계산합니다.
6. DFS(int node, int distance): 깊이 우선 탐색 함수를 구현하여 재귀적으로 각 정점을 탐색하며 거리를 업데이트합니다.

테스트 케이스

작성한 코드를 다음과 같은 테스트 케이스로 검증할 수 있습니다:

테스트 입력

예상 출력

설명

위의 입력으로부터 트리를 그려보면 다음과 같습니다:

트리의 지름은 노드 2에서 시작하여 노드 4까지 가는 경로로, 총 길이는 3 + 2 + 4 = 9입니다.

마치며

오늘은 C#을 활용하여 트리의 지름을 구하는 문제를 풀어보았습니다.
이 알고리즘은 트리 문제에서 매우 자주 출제되는 유형이므로, 충분히 연습하시기를 권장합니다.
여러 가지 테스트 케이스를 시도해보며 이해를 깊이 해보세요.
감사합니다!