[Python] 백준 1967 트리의 지름

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

1967번: 트리의 지름

 

문제 해결

- 간선에 가중치(거리)가 있다.

- 부모 자식 관계는 중요하지 않다. 그냥 노드와 노드사이의 가중치 합이 큰 것을 찾아야 한다.

- 제일 위에 있는 1에서 시작해서 가장 멀리 있는 것을 찾아본다. 이거는 BFS나 DFS 둘다 가능할 것이다.

- 가장 멀리 있는 인덱스에서 다시 시작해서 가장 멀리 있는 노드까지 가중치(거리) 합을 구한다. 이 것이 정답.

- 유사문제와 거의 비슷하다. 다른점은 가중치 존재 여부

유사 문제

https://thought-process-ing.tistory.com/32

백준 1167 트리의 지름

코드(BFS)

import sys
input = sys.stdin.readline
from collections import deque
def bfs(start):
    visited = [-1 for _ in range(n+1)]
    visited[start] = 0
    que = deque()
    que.append((start,0))
    maximum = [0,0]
    while que:
        now, way = que.popleft()
        for next, distance in graph[now]:
            if visited[next] == -1:
                visited[next] = way+distance
                que.append((next,visited[next]))
                if maximum[1] < visited[next]:
                    maximum = next, visited[next]
    return maximum

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))
node, distance = bfs(1)
node, distance = bfs(node)
print(distance)