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

1. 문제 정의

주어진 트리의 지름을 구하는 문제입니다. 트리의 지름은 두 노드 간의 최장 경로의 길이를 말합니다. 트리는 노드와 간선으로 구성된 그래프로, 사이클이 없는 연결 그래프입니다. 이 문제를 해결하기 위해 DFS(Depth First Search) 또는 BFS(Breadth First Search) 알고리즘을 사용할 수 있습니다.

2. 문제 입력

첫 번째 줄에 노드의 개수 N이 주어집니다. 다음 줄부터 N-1개의 줄에는 간선이 주어지며, 각 간선은 두 개의 정수 a와 b로 표현됩니다. 이는 노드 a와 노드 b 사이에 간선이 존재함을 의미합니다.

입력 예시

    5
    1 2
    1 3
    2 4
    2 5

3. 문제 출력

트리의 지름을 출력합니다.

출력 예시

    3

4. 알고리즘 설명

트리의 지름을 구하기 위한 알고리즘은 다음과 같은 단계로 진행됩니다:

  1. 트리를 인접 리스트 형태로 저장합니다.
  2. 첫 번째 DFS를 통해 가장 멀리 있는 노드를 찾습니다.
  3. 두 번째 DFS를 사용해 첫 번째 DFS에서 찾은 노드로부터 가장 멀리 있는 노드를 찾습니다.
  4. 두 번째 DFS의 결과가 트리의 지름입니다.

5. C++ 코드 구현

트리의 지름을 계산하는 C++ 코드는 아래와 같습니다:


#include 
#include 
#include 

using namespace std;

vector> tree;
vector visited;

int furthestNode(int node) {
    visited[node] = true;

    int maxDistance = 0;
    int farthestNode = node;

    for (int neighbor : tree[node]) {
        if (!visited[neighbor]) {
            int distance = furthestNode(neighbor) + 1;
            if (distance > maxDistance) {
                maxDistance = distance;
                farthestNode = neighbor;
            }
        }
    }

    return farthestNode;
}

int main() {
    int N;
    cin >> N;

    tree.resize(N + 1);
    visited.resize(N + 1, false);

    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    int farthestFromStart = furthestNode(1);
    
    fill(visited.begin(), visited.end(), false);
    
    int diameterEnd = furthestNode(farthestFromStart);
    
    cout << diameterEnd << endl;

    return 0;
}

6. 코드 설명

코드는 아래와 같은 구조로 이루어져 있습니다:

  1. 라이브러리를 포함하고, 전역 변수를 선언합니다.
  2. furthestNode 함수를 통해 DFS를 수행하며 가장 멀리 있는 노드를 반환합니다.
  3. 메인 함수에서 입력을 받고, 트리를 구성합니다.
  4. 첫 번째 DFS를 통해 시작 노드에서 가장 멀리 있는 노드를 찾습니다.
  5. 두 번째 DFS를 통해 첫 번째 DFS에서 찾은 노드로부터 가장 멀리 있는 노드를 찾고, 이 노드가 지름의 끝입니다.
  6. 지름의 길이를 출력합니다.

7. 시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)입니다. N개의 노드를 방문하는 과정에서 각 노드에 대해 DFS를 수행하기 때문에, 트리의 크기에 비례합니다.

8. 결론

이번 강좌에서는 트리의 지름을 구하는 문제를 해결하는 방법을 알게 되었습니다. DFS를 활용하여 트리의 구조를 탐색하고 솔루션을 도출하는 과정을 이해하는 것이 중요합니다. 다양한 그래프 문제를 연습함으로써 알고리즘 실력을 향상시키길 바랍니다.

9. 참고 자료