[백준 1967] 트리의 지름(python)

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

트리의 지름 문제

트리에 존재하는 경로들 중에서 가장 긴 것의 길이인 지름을 구하는 문제

 

#사용 알고리즘

깊이 우선 탐색

트리

 

📌문제 접근 포인트

1. 트리의 경로 중에 가장 긴 것을 찾아야한다. 가장 긴 것을 찾는 방법을 생각해보자.
2. 트리는 사이클이 없는 그래프이므로, 임의의 노드에서 가장 먼 지점은 항상 트리의 끝 노드이기에 임의의 노드(루트 노드)에서 가장 거리가 먼 점 x를 찾고, 다시 x에서 가장 거리가 먼 점 y를 찾으면 트리의 지름이다.
증명 과정은 다음과 같다.
☆임의의 노드 A에서 시작하여 가장 먼 점을 B, B를 기준으로 가장 먼 점를 C라고 가정해보자.
1) 가장 먼 지점 B가 트리의 끝 노드가 아닐 경우 (B보다 먼 노드 X가 존재한다 해보자.)
→ A에서 B까지의 거리 ≤  A에서 X까지의 거리(B가 X보다 멀리 있는 노드이므로)가 성립하게 되므로,
☆과 모순이 되므로 성립할 수 없으므로 반드시 끝 노드이다.
2) 가장 먼 지점 B가 트리의 끝 노드 일 경우
B로부터 멀리 있는 노드가 존재하지 않으므로, B에서 다른 모든 노드까지의 거리는 지름보다 큰 값이 나오지 않게 된다.
그러므로 B에서 가장 먼 지점 C까지의 거리가 트리의 지름이 된다.
3. DFS(혹은 BFS)를 이용해서 임의의 노드로부터 가장 먼 지점을 구해주고, 그 지점에서 다시 DFS(혹은 BFS)를 이용하여 가장 먼 지점까지의 거리를 구하면 트리의 지름을 얻을 수 있다.

⚙ 내가 푼 정답 코드 (DFS 활용)

def find(start, now): # 가장 먼 지점 찾기
    for a, b in tree[start]:
        if visited[a] == -1:
            visited[a] = b + now
            find(a, visited[a])

import sys
sys.setrecursionlimit(1000000)
n = int(sys.stdin.readline())
tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    p, c, w = map(int, sys.stdin.readline().split())
    tree[p].append([c,w])
    tree[c].append([p,w])

visited = [-1]*(n+1)
visited[1] = 0
find(1,0) # 가장 먼 지점을 먼저 찾고

start = visited.index(max(visited))
visited = [-1]*(n+1)
visited[start] = 0 
find(start,0) # 다시 가장 먼 지점을 찾아주자.
print(max(visited))