[백준] CLASS 4 달성하기 3일차

이진규·2022년 7월 28일
1

백준(PYTHON)

목록 보기
59/115

1. 트리의 지름(★BFS)

링크 : https://www.acmicpc.net/problem/1167

  • 트리의 지름은 아무 노드에서 bfs(dfs도 무관)를 통해 가정 멀리있는 노드를 구한 후 해당 노드에서 bfs를 한번더 진행하여 가장 멀리있는 노드를 구하면 된다.
from collections import deque
from sys import stdin
input = stdin.readline

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

for _ in range(n):
    c = list(map(int, input().split()))
    for i in range(1, len(c)-2, 2):
        graph[c[0]].append((c[i], c[i+1]))

def bfs(v, sum_edge):
    visited = [False] * (n+1)
    visited[v] = True
    q = deque([(v, sum_edge)])
    idx, max_edge = 0, 0 # 인덱스와 edge거리

    while q:
        node, sum_edge = q.popleft()

        if max_edge < sum_edge: # edge거리가 갱신될때마다 인덱스와 edge거리를 업데이트 해준다.
            idx = node
            max_edge = sum_edge

        for i, edge in graph[node]:
            if not visited[i]:
                visited[i] = True
                q.append((i, sum_edge + edge))

    return idx, max_edge

node, edge = bfs(1, 0) # 첫번 째 : 아무 노드에서 가장 멀리 있는 노드를 구하는 경우
node, edge = bfs(node, 0) # 두번 째 : 가장 멀리 있는 노드에서 다시 멀리 있는 노드를 구하는 경우
print(edge)
profile
항상 궁금해하고 공부하고 기록하자.

0개의 댓글