보통 1명 해결 정답률 100.0%

Tree Diameter

A tree is a connected undirected graph with no cycles.

배우게 될 내용

  • 순회로 가장 먼 노드 찾기
  • BFS 두 번으로 지름 구하기
  • 인접 리스트로 트리 표현하기

문제

A tree is a connected undirected graph with no cycles. Its diameter is the largest number of edges on a path between any two vertices. Return that length; you do not need to return the path. No root is specified.

Implement tree_diameter(vertices, edges).

Input

vertices: The number of vertices.

edges: Undirected connections [u, v].

Output

Return the diameter measured in edges, not vertices.

제약 조건

1 ≤ vertices ≤ 200,000. Exactly vertices − 1 edges, with distinct endpoints in 1…vertices. Inputs always form a tree. A one-vertex tree has diameter 0.

예시

예시 1
입력:
vertices = 5
edges = [
    [1, 2],
    [2, 3],
    [3, 4],
    [2, 5]
]

예상 출력:
expected = 3
입력:
long long vertices = 5;
std::vector<std::vector<long long>> edges = {
    {1, 2},
    {2, 3},
    {3, 4},
    {2, 5}
};

예상 출력:
long long expected = 3;
입력:
long vertices = 5;
long[][] edges = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3},
    new long[] {3, 4},
    new long[] {2, 5}
};

예상 출력:
long expected = 3;

설명

The path 5–2–3–4 contains three edges. No path in this tree is longer.

예시 2
입력:
vertices = 1
edges = []

예상 출력:
expected = 0
입력:
long long vertices = 1;
std::vector<std::vector<long long>> edges = {};

예상 출력:
long long expected = 0;
입력:
long vertices = 1;
long[][] edges = new long[][] {};

예상 출력:
long expected = 0;

설명

A single vertex has no edges, so the longest path length is 0.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

트리에서는 모든 정점 쌍을 다 보지 않고도 두 번의 그래프 탐색으로 최장 경로를 찾을 수 있습니다.

힌트 2

아무 정점에서 시작해 가장 먼 정점을 찾고, 그 정점에서 다시 탐색해 최장 거리를 구하세요.

힌트 3

정점 수가 아니라 간선 수를 세고, 정점이 하나뿐인 트리의 지름은 0입니다.

예상 복잡도

시간 O(vertices), 추가 공간 O(vertices)

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

# 코더 언어 시간 메모리 AI 평가 풀이
1 ННикита Python 825 ms - 5/5 코드 보기

다른 사람의 풀이 보기

커뮤니티 솔루션

스포일러: 아래에 1개 전체 솔루션 있음 먼저 직접 풀어보세요. 다른 개발자의 코드와 AI 리뷰도 참고할 수 있습니다. 로그인하고 문제를 풀면 토론에 참여할 수 있습니다.