Lv.3bfsdfstree
트리에서 가장 먼 두 마을
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
0번부터 n - 1번까지 n개의 마을이 n - 1개의 양방향 도로로 이어져 있고, 어떤 두 마을 사이에도 길이 정확히 하나 있습니다(트리).
roads[i] = [a, b, len]은 a와 b를 잇는 길이 len의 도로입니다.
두 마을 사이의 거리는 그 사이 길에 있는 도로 길이의 합입니다. 가장 멀리 떨어진 두 마을 사이의 거리를 반환하세요. 마을이 하나면 0입니다.
입출력 예
| n | roads | result |
|---|---|---|
5 | [[0, 1, 3], [1, 2, 4], [1, 3, 2], [3, 4, 6]] | 12 |
2 | [[0, 1, 7]] | 7 |
1 | [] | 0 |
입출력 예 설명
예 1 — 2번에서 4번까지 4 + 2 + 6 = 12가 가장 깁니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(n: int, roads: int[][]) → long
제한 사항
-
n,roads.length roads[i] = [a, b, len], ,- 도로들은 하나의 트리를 이룹니다. 답은 32비트 정수를 넘을 수 있습니다.
기대 복잡도
- 시간
- O(N)
- 공간
- O(N)
입출력 예
| n | roads | 기대 출력 |
|---|---|---|
5 | [[0,1,3],[1,2,4],[1,3,2],[3,4,6]] | 12 |
2 | [[0,1,7]] | 7 |
1 | [] | 0 |
힌트
힌트
두 번의 탐색으로 충분합니다.
- 아무 마을(예: 0번)에서 가장 먼 마을
u를 찾습니다. u에서 가장 먼 마을까지의 거리가 답입니다.
1단계에서 찾은 u는 반드시 가장 긴 경로의 한쪽 끝이라는 성질이 있습니다.
트리라서 BFS/DFS 한 번이 곧 모든 마을까지의 거리를 줍니다(가중치가 있어도 경로가 하나뿐이니 다익스트라가 필요 없습니다). 마을이 20만 개라 한 줄로 이어진 트리에서는 재귀 DFS가 스택 오버플로를 낼 수 있으니 스택/큐로 반복문을 쓰세요.
복잡도 목표
모든 마을에서 탐색을 한 번씩 하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 294 ms | 추정 |
| C++ (GCC, gnu++23) | 294 ms | 도출됨 |
| Python 3.13 | 1108 ms | 도출됨 |
| Java 25 | 1632 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1588 ms | 추정 |
| C# 14 (.NET 10) | 1588 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 7 | 판정만 |
| performance | 60 | 4 | 판정만 |