[백준] 트리의 지름

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

1967번: 트리의 지름

dfs를 사용하는 문제입니다. 

 

이전에 해결했던

https://life318.tistory.com/58

[백준] 트리의 지름

문제와 완전히 동일하고, 그래프의 정보를 받아오는 부분만 다릅니다. 

 

<Solution>

실제 구현은 아래와 같습니다.

import sys

N = int(sys.stdin.readline().rstrip())

graph = [[] for _ in range(N+1)]

for _ in range(N-1):
    start, end, cost = list(map(int,sys.stdin.readline().rstrip().split()))
    graph[start].append((end, cost)) 
    graph[end].append((start, cost))

before = 0
for i, e in enumerate(graph[1:]):
    e.sort()
    tmp = []
    before = 0
    for index, e_ in enumerate(e):
        if index == 0:
            tmp.append(e_)
            before = e_[0]
            continue
        if before != e_[0]:
            tmp.append(e_)
            before = e_[0]
    graph[i+1] = tmp 

# dfs(from random node)
stack = [[1,0]]
visited = [False] * (N+1)
max_distance = 0
max_node = 0
while(stack):
    node, distance = stack.pop()
    # check max distance
    if distance > max_distance:
        max_distance = distance
        max_node = node
    if visited[node]:
        continue
    else: 
        visited[node] = True
    for n in graph[node]:
        if not visited[n[0]]:
            stack.append([n[0], distance+n[1]])

# print(f'max_node,max_distance = {max_node, max_distance}')

# dfs(from max_node)
stack = [[max_node,0]]
visited = [False] * (N+1)
max_distance = 0
max_node = 0
while(stack):
    node, distance = stack.pop()
    # check max distance
    if distance > max_distance:
        max_distance = distance
        max_node = node
    if visited[node]:
        continue
    else: 
        visited[node] = True
    for n in graph[node]:
        if not visited[n[0]]:
            stack.append([n[0], distance+n[1]])
# print(f'max_node,max_distance = {max_node, max_distance}')

print(max_distance)