[baekjoon / Python] 1167 트리의 지름

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

comment

아니 dfs로 풀려다가 안풀려서 개빡침. dfs 함수자체는 간단한데 메인이 조금 더러워지네. 노드 중 가장 높은 높이를 가지는 것을 찾아서 이제 dfs 다시 돌리면 되겠다했는데 생각만하고 어칼지는 모르겠음. 헤매다 답봄 dfs 매개변수 계속 줄랬는데 max(visited)로 index찾아쓰네.. 굿

알고리즘

이게 임의의 노드에서 가장 먼 노드를 찾아서 그 노드에서 단말노드까지의 길이를 구하면 된다. 임의의 노드에서 가장 먼노드가 내가 생각한 가장 높은 높이를 가지는 단말인 것 같다.
답을 보면 참 쉬운데 백준에서 그 이해하기 쉬운 설명을 봤음.
트리에서 노드를 구슬이라 가정하고 그 구슬끼리 잇는 실을 간선이라 생각하면, 아무거나 챡 구슬 잡아서 손으로 집어서 위로 올리면(y축-x,y,z축 중에서) 구슬들이 다 실에 연결되서 밑으로 축 처지잖. 거기서 가장 아래에 있는 구슬을 잡으면 그 맨밑에 축처진 구슬까지의 길이가 최대다!

그림 그리면서 생각해봤는데 트리 높이가 크다고 길진않은듯 만약에 저 그림에서 아닌가?ㅋㅋ 뭐 쩃든 저래됨

bfs 답보고 dfs도 둘다함 억울해서

코드

from collections import deque

V = int(input())
line = [[] for i in range(V+1)]

for i in range(1,V+1):
   li = list(map(int,input().split()))
   for j in range(1,len(li),2):
       if li[j] != -1:
           line[li[0]].append([li[j],li[j+1]])

def bfs(v):
   visited = [-1 for i in range(V+1)]
   visited[v] = 0
   q = deque()
   q.append(v)
   maxD,maxV = 0,0

   while q:
       cur = q.pop()
       for e,w in line[cur]:
           if visited[e] == -1:
               visited[e] = visited[cur]+w
               q.append(e)
               if maxD<visited[e]:
                   maxD,maxV = visited[e],e
   return maxD,maxV

def dfs(v,maxD):
   for e,w in line[v]:
       if visited[e] == -1 :
           visited[e] = maxD + w
           dfs(e,visited[e])

visited = [-1 for i in range(V+1)]
visited[1] = 0
dfs(1,0)
maxV = visited.index(max(visited))
visited = [-1 for i in range(V+1)]
visited[maxV] = 0
dfs(maxV,0)
print(max(visited))

# td,maxV = bfs(1)
# print(bfs(maxV)[0])