[백준][Python] 1167번 트리의 지름

DFS 풀이

import sys
sys.setrecursionlimit(1000000)

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

def dfs(v,weight):
    
    visited[v] = 1
    result[v] = weight
    
    for i in graph[v]:
        
        node, length = i
        
        if visited[node] == 0:
            if result[node] == -1 :
                
                dfs(node,weight + length)

visited = [0 for _ in range(n+1)]
result = [-1 for _ in range(n+1)]
dfs(1,0)                

node = result.index(max(result))

visited = [0 for _ in range(n+1)]
result = [-1 for _ in range(n+1)]
dfs(node,0)
print(max(result))

BFS 풀이

from collections import deque

def bfs(v,weight):
    
    queue = deque()
    queue.append((v,weight))
    visited[v] = 1
    result[v] = 0
    
    while queue:
        
        v,weight = queue.popleft()
        
        for i in graph[v]:
            
            node,length = i
            
            if visited[node] == 0:
                if result[node] == -1:
                    
                    result[node] = weight + length
                    queue.append((node,result[node]))
                    visited[node] = 1

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

node = result.index(max(result))

visited = [0 for _ in range(n+1)]
result = [-1 for _ in range(n+1)]
bfs(node,0)
print(max(result))