✓

태그:

27. 트리 CLASS 4 ESSENTIAL

1967번에서는 그랬지만 모든 점에서 거리를 잴 필요는 없어요!

풀이 비스무리한거 보기

트리의 지름을 구하는 문제입니다. 1967번 - 트리의 지름 문제와는 입력 방식과 조건의 일부 차이를 제외하면 같은 문제입니다. 다만 이 조건의 일부 차이(정점 개수 10000 → 100000)가 좀 그렇습니다. 이 때문에 모든 점에 대해 각 점을 시작점으로 해서 DFS를 돌리는 것은 시간 초과가 됩니다. 따라서 DFS를 좀 덜 돌려야되는데, 이건 아무 점이나 잡고 최장 거리를 찾는 DFS를 두 번만 돌리면 그게 그래프에서의 최장 거리가 됩니다. 직관적으로는 이해가 되는데 증명은 못하겠군요. 아무데서나 DFS 두 번만 돌리면 그게 최장거리입니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-10 19:12:00

---