본문 바로가기

DFS #깊이우선탐색 #1167 #트리의 지름 #백준 #BOJ1

[BOJ] 1167 : 트리의 지름 문제 링크 1167번: 트리의 지름 (acmicpc.net) 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 임의의 두 정점 사이의 거리중 가장 긴 거리를 찾는 문제 당연히 루트노드에서 탐색을 시작하면 가장 긴 거리를 찾을 수 있을 것이라 생각. 하지만 루트노드에서 탐색하면 모든 정점은 방문할 수 있겠지만 모든 경로를 탐색하지는 못했다. 그렇다고 모든 정점에서 부터 탐색을 할 것인가?? 그럼 시간초과가 난다. 해결 1. 루트노드에서 탐색을 시작해 가장 깊은 노드를 찾는다. (여기서 가장 .. 2022. 2. 9.

이전 1 다음

티스토리툴바