BOJ 백준 파이썬 1967 트리의 지름

가장 근본적인 방식은 모든 정점에서 시작해보는 완전 탐색일 것이다.

한 정점과 한 정점 사이의 최대 거리니까

하지만, dfs로 시도해보니 시간초과가 나고 bfs로 시도해보니 

간당간당하게 통과한다.

결국 목적은 코딩테스트 통과고

문제 풀이니 미리 푸는 개념을 알면 장땡이다.

 

1)임의의 한 노드에서 시작해서 가장 거리가 먼 노드를 찾고

2)그 노드에서 가장 먼 노드를 찾아주면 된다.

3) 1,2 과정에서 구한 거리를 더해주면 된다.

 

 

import sys
from collections import deque
from itertools import combinations
from typing import List, Literal
 
 
sys.setrecursionlimit(100000)
 
def dfs(x,depth):
    global res,node
    #print(x+1,depth)
    for y,ln in graph[x]:
        if ch[y]==-1:
            ch[y]=1
            if res<depth+ln:
                res=depth+ln
               # print(y,res)
                node=y
            dfs(y,depth+ln)
            ch[y]=-1
                
if __name__=='__main__':
   # sys.stdin=open("input2.txt", "rt")
    n=int(input()) ##노드의 갯수
 
    graph=[[]*n for _ in range(n)]
 
    #dist=[[-1]*n for _ in range(n)] ##가중치의 길이 저장
    ch=[-1]*n
    for _ in range(n-1):
        a,b,c=map(int,input().split()) ##a=부모 노드,b=자식 노드,c=노드와 노드 간의 길이(가중치)
        a-=1
        b-=1
        graph[a].append([b,c])
        graph[b].append([a,c])
        
    ch=[-1]*n
    ch[0]=1
    res=0
    node=0 ##가장 먼 노드
    dfs(0,0)
    ch=[-1]*n
    ch[node]=1
    res=0
    dfs(node,0)
    print(res)