[python3] 백준 1967 풀이 (트리의 지름, DFS)

이 문제는 그림을 보면 이해가 빨라진다.

우리는 각 노드를 쫙 잡아당겼을때 길이가 가장 길어지도록 하는 길이를 찾아야 한다.

만약 오른쪽 그림이 가장 길게 잡아당겨진 형태라고 가정한다.

그럼 오른쪽에 회색 노드들 중에서 아무거나 잡고 DFS를 통해 가장 먼 노드를 찾으면 그건 무조건 파란색 노드가 된다.

신기하게도 어떤 노드를 택하던 가장 먼 노드를 찾으면 그건 파란색 노드가 되는것이다. 진짜 신기하다.

 

그렇게 파란색 노드를 하나 찾고, 이번에 찾은 파란색 노드로부터 가장 먼 길이를 찾으면 우리가 찾고자하는 트리의 길이가 된다......

 

그럼 DFS를 단 2번만 하면 해결되는 문제이다.

그럼 DFS할 때 각 길이만 저장하면서 확인하면 되는 것이다.

1. DFS(1)로 파란색 노드하나 찾기

2. DFS(BlueNode)로 반대쪽 파란색 노드 찾으며 길이구하기

3. 길이 출력

 

import sys
input = sys.stdin.readline

n = int(input())
M =[[]for i in range(n+1)]

for i in range(n-1):
    a,b,c = map(int, input().split())
    M[a].append([b,c])
    M[b].append([a,c])

def DFS(node):
    s = [[node,0]]
    visited = [0 for i in range(n+1)]
    big = 0
    leaf = 0
    while s:
        node,length = s.pop()
        visited[node] = 1
        nodelist = M[node]
        if len(nodelist) == 1: #leaf노드일경우 length를 big와 비교
            if length > big:
                big = length
                leaf = node
        for node in nodelist:
            if visited[node[0]] == 0:
                s.append([node[0],node[1]+length])

    return leaf, big
node,legth = DFS(1)
node,legth = DFS(node)
print(legth)

처음에는 이해가 안가서 왜 DFS를 써야하는지 몰랐는데 그림을 보고 팀원의 설명을 들으니 한번에 이해가 갔다. 진짜 신기한 문제다.