Funcia
Lv.3bfsdfstree

트리에서 가장 먼 두 마을

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

0번부터 n - 1번까지 n개의 마을이 n - 1개의 양방향 도로로 이어져 있고, 어떤 두 마을 사이에도 길이 정확히 하나 있습니다(트리). roads[i] = [a, b, len]은 a와 b를 잇는 길이 len의 도로입니다.

두 마을 사이의 거리는 그 사이 길에 있는 도로 길이의 합입니다. 가장 멀리 떨어진 두 마을 사이의 거리를 반환하세요. 마을이 하나면 0입니다.

입출력 예

nroadsresult
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

제한 사항

  • 1≤1 \le n ≤200,000\le 200{,}000, roads.length =n−1= n - 1
  • roads[i] = [a, b, len], 0≤a,b<n0 \le a, b < n, 1≤len≤1061 \le len \le 10^6
  • 도로들은 하나의 트리를 이룹니다. 답은 32비트 정수를 넘을 수 있습니다.

기대 복잡도

시간
O(N)
공간
O(N)

입출력 예

nroads기대 출력
5[[0,1,3],[1,2,4],[1,3,2],[3,4,6]]12
2[[0,1,7]]7
1[]0

힌트

힌트

두 번의 탐색으로 충분합니다.

  1. 아무 마을(예: 0번)에서 가장 먼 마을 u를 찾습니다.
  2. u에서 가장 먼 마을까지의 거리가 답입니다.

1단계에서 찾은 u는 반드시 가장 긴 경로의 한쪽 끝이라는 성질이 있습니다.

트리라서 BFS/DFS 한 번이 곧 모든 마을까지의 거리를 줍니다(가중치가 있어도 경로가 하나뿐이니 다익스트라가 필요 없습니다). 마을이 20만 개라 한 줄로 이어진 트리에서는 재귀 DFS가 스택 오버플로를 낼 수 있으니 스택/큐로 반복문을 쓰세요.

복잡도 목표

모든 마을에서 탐색을 한 번씩 하는 O(N2)O(N^2) 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)294 ms추정
C++ (GCC, gnu++23)294 ms도출됨
Python 3.131108 ms도출됨
Java 251632 ms도출됨
Kotlin 2.4 (JVM)1588 ms추정
C# 14 (.NET 10)1588 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness407판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.