[Python] 백준 / gold / 1967 : 트리의 지름

문제 링크 : https://www.acmicpc.net/problem/1967

트리의 지름에 대해선 전에 공부한적이 있어서 쉽게 풀 수 있었다. https://velog.io/@heyksw/트리의-지름

BFS 로 푸는게 편한 문제인데, 연습할 겸 일부러 DFS로 풀어봤다. 조심할 점은 루트에서 가장 먼 두 곳으로 뻗어나가는 것이 아니라, 루트에서 가장 먼 노드를 찾고, 그 노드에서 다시 DFS 를 수행해서 다시 가장 먼 노드를 찾는다는 거다.

그리고 visit 리스트를 초기화 할 때 for v in visit 이렇게 조건을 걸어주면 소용이 없고 꼭 인덱스로 접근해서 값을 변경해줘야 실제로 변경이 적용된다.

파이썬 코드

import sys
sys.setrecursionlimit(10**6)
N = int(sys.stdin.readline())
tree = [[] for _ in range(N+1)]

for _ in range(N-1):
    a, b, c = map(int, sys.stdin.readline().split())
    tree[a].append((b, c))
    tree[b].append((a, c))

leaf = []
visit = [False] * (N+1)


def dfs(node, distance):
    visit[node] = True
    end = True

    for x in tree[node]:
        if not visit[x[0]]:
            end = False
            dfs(x[0], distance + x[1])

    if end:
        leaf.append((node, distance))


dfs(1, 0)
leaf.sort(key=lambda x : x[1])
point1 = leaf[-1]

leaf.clear()
for i in range(len(visit)):
    visit[i] = False

dfs(point1[0], 0)
leaf.sort(key=lambda x:x[1])

point2 = leaf[-1]

print(point2[1])