[python] 백준 18126 너구리 구구

18126번: 너구리 구구 (acmicpc.net)

18126번: 너구리 구구

 

BFS

출발지는 항상 1

bfs를 사용해서 갈 수 있는 모든 노드를 방문하고 최대값을 계속 갱신

from collections import deque

def bfs(s):

    global result

    que=deque()

    que.append((s,0)) #처음 출발지인 1과 가중치 0을 넣음

    while(que): #큐가 있을 때까지 반복

        v,c=que.pop()

        visited[v]=True #방문처리

        result=max(result,c) #최대값 갱신

        for i in range(1,N+1): #모든 노드 방문

            if(visited[i]): continue #이미 방문했다면 넘어가기

            if(adj[v][i]!=0): #연결되어있다면

                que.append((i,c+adj[v][i])) #지금까지 가중치+갈 수 있는 가중치

N = int(input())

adj=[[0]*(N+1) for _ in range(N+1)] #1번부터 N번까지 쓸 거야

visited=[False]*(N+1) #방문처리

result=0

for i in range(N-1):

    f,t,v=map(int,input().split())

    adj[f][t]=v

    adj[t][f]=v

bfs(1)

print(result)