[백준] 1967번-(Python 파이썬) - Tree, dfs, bfs, Dijkstra

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

이번 문제는 1167번 문제와 거의 같은 문제이다. 풀이도 1167번 문제 풀이에 적어놨으니 참고하면 된다.

bfs를 이용한 풀이

import sys
from collections import deque
input = sys.stdin.readline

v = int(input())
graph = [[] for _ in range(v+1)]
for _ in range(v-1):
  a = list(map(int, input().split()))
  graph[a[0]].append([a[1], a[2]])
  graph[a[1]].append([a[0], a[2]])
  
def bfs(start):
  q = deque()
  q.append(start)
  visit = [-1] * (v + 1)
  visit[start] = 0
  max_ = [0, 0]
  while q:
    temp = q.popleft()
    for i, j in graph[temp]:
      if visit[i] == -1:
        visit[i] = visit[temp] + j
        q.append(i)
        if max_[0] < visit[i]:
          max_ = visit[i], i
  
  return max_

dis, node = bfs(1)
dis, node = bfs(node)

print(dis)

dijkstra를 이용한 풀이

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
inf = sys.maxsize

v = int(input())
graph = [[] for _ in range(v + 1)]
for _ in range(v - 1):
    parent, node, w = map(int, input().split())
    graph[parent].append([node, w])
    graph[node].append([parent, w])

def dijkstra(start):
    heap = []
    heappush(heap, [0, start])
    dp = [inf for _ in range(v + 1)]
    dp[start] = 0

    while heap:
        w, n = heappop(heap)
        for n_n, wei in graph[n]:
            n_w = wei + w
            if n_w < dp[n_n]:
                dp[n_n] = n_w
                heappush(heap, [n_w, n_n])
    
    return dp

d = dijkstra(1)
f_node = d.index(max(d[1:]))
d_ = dijkstra(f_node)
ans = max(d_[1:])
print(ans)