[백준] 1967 트리의 지름

백준 1967번 트리의 지름

그래프 / 파이썬

 

 

[문제]

 

 

 

[과정]

※ 핵심 키워드 : 트리의 지름 구하는 공식

• 임의의 노드에서 가장 먼 길이에 있는 노드구하기
• 구해진 노드에서 가장 먼 길이에 있는 노드를 구하기

 

이렇게 bfs를 두번을 돌게되면 트리의 지름을 구할 수 있다.

만약 for문으로 모든 노드의 수만큼 돌리게 되면 파이썬으로 시간초과가 발생한다.

 

 

1. bfs에서 리턴값으로 가장 먼 노드와 해당 노드까지의 길이를 반환한다.
2. 반환된 노드값을 한번 더 bfs를 돌리고 여기서 반환된 길이(dist)를 출력한다.

 

 

 

 

[소스코드]

 

# 1967 트리의 지름

from collections import deque

n = int(input())
graph = [[] for _ in range(n+1)]

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

def bfs(graph, start):
    visited = [False] * (n+1)
    distance = [0] * (n+1)

    q = deque([start])
    visited[start] = True

    while q:
        v = q.popleft()
        for i in graph[v]:
            if not visited[i[0]]:
                q.append(i[0])
                visited[i[0]] = True
                cost = distance[v] +i[1]
                if cost > distance[i[0]]:
                    distance[i[0]] = cost
    return distance.index(max(distance)), max(distance)

node, dist = bfs(graph, 1)
node, dist = bfs(graph, node)
print(dist)

 

 

 

---

 

 

 

[통과]

 

 

 

1167번도 트리의 지름이고 내용도 입력값만 다를뿐 다 같은데 왜 틀리는지 모르겠다ㅠㅠ

왜그럴까...