Baekjoon 1967번 트리의 지름

💭 문제가 궁금하다면?

내가 시도한 방법

• 인접 리스트 활용
  • 두 노드 사이의 거리를 쉽게 기록해야하기 인접 행렬을 사용했다가 메모리초과가 발생해서 인접 리스트로 다시 구현
• visited에 방문 여부 + 해당 노드까지의 거리 정보 담아내기
• 문제 접근 방식은 아무리 고민해도 떠오르지 않아 해당 블로그 참고
  • https://bedamino.tistory.com/15

def DFS(node):
    visited = [-1] * (N + 1)
    visited[node] = 0
    stack = [node]

    far_node_diff = [0, 0]

    while stack:
        v = stack.pop()

        for nv, nw in weights[v]:
            
            if visited[nv] < 0:
                stack.append(nv)
                visited[nv] = visited[v] + nw

                if far_node_diff[1] < visited[nv]:
                    far_node_diff = [nv, visited[nv]]

    return far_node_diff


N = int(input())
weights = [[] for _ in range(N+1)]

for _ in range(N-1):
    parent, child, weight = map(int, input().split())
    weights[parent].append([child, weight])
    weights[child].append([parent, weight])

start, diff = DFS(1)
end, diff = DFS(start)
print(diff)