흙금이네 블로그

[BOJ] 18126 - 너구리 구구 (Python) 본문

알고리즘

[BOJ] 18126 - 너구리 구구 (Python)

흙금 2023. 4. 15. 20:32

 

 

아이디어

 

BFS로 입구에서 가장 멀리 떨어진 방까지의 거리를 출력한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

def solution():
    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))
    visited = [-1]*(N+1)
    visited[1] = 0
    stack = [1]
    while stack:
        u = stack.pop()
        for v, c in graph[u]:
            if visited[v] == -1:
                visited[v] = visited[u]+c
                stack.append(v)
    print(max(visited))

solution()

 

Comments