Baekjoon Online Judge 1167번 파이썬

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

1167번: 트리의 지름

잘못 푼 코드

import sys
sys.setrecursionlimit(10 ** 9)

def dfs(start,result):
  visited[start] = True
  for i in graph[start]:
    if not visited[i]:
      result += distance[start][i]
      print(result)
      dfs(i)
      
V = int(sys.stdin.readline())

inputs = []
for i in range(V):
  inputs.append(list(map(int,sys.stdin.readline().split()))) 

visited = [False] * (V+1)

distance=[[0]*(V+1) for i in range(V+1)]
graph=[[] for i in range(V+1)]
for input in inputs:
  for i in range(1, len(input)-2,2):
    distance[input[0]][input[i]] = input[i+1]
    graph[input[0]].append(input[i])
print(distance)
print(graph)

result1= [-1] * (V+1)
result1= 0
dfs(1,result1)

이 코드로 풀 수는 있을 것 같지만,
graph, distance, visited. 총 3개의 배열을 불필요하게 사용하고 있다고 느꼈다.

트리의 지름을 구하는 방법을 기억해두어야겠다.

정답 코드

import sys
sys.setrecursionlimit(10**9)

V=int(sys.stdin.readline())

graph=[[]for _ in range(V+1)]
for i in range(V):
    input=list(map(int,sys.stdin.readline().split()))
    for i in range(len(input[1:])):
        if i % 2 == 1:
            graph[input[0]].append((input[i],input[i+1]))

def dfs(start,result):
    for x, y in graph[start]:
        if result[x] == -1:
            result[x]= result[start] + y
            dfs(x,result)

result1=[-1] * (V+1)
result1[1] = 0
dfs(1,result1) #아무 노드에서 시작

max_value = max(result1) #가장 긴 거리 구하기
node_far = result1.index(max_value) #시작점에서 가장 거리가 먼 노드의 번호

#최장 거리 노드에서 다시 dfs
result2 = [-1] * (V+1)
result2[node_far] = 0
dfs(node_far,result2)
print(max(result2))