[백준 1967] 트리의 지름 - python (solved.ac - 골드 5)

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

풀이

문제를 보았을때 알수있는 힌트

이전에 풀었던 백준 1167번 문제와 유사한 문제이다.

그것보다는 쉬운문제이니 유사하게 접근하면 쉽게 풀 수 있다.

먼저 그래프를 생성한 후 아무 위치를 하나 잡고(여기서 저는 1번을 기준으로 잡았습니다.) 최대로 먼 곳을 찾는다.

이후 먼 곳에서 부터 다시 최대로 먼곳을 찾으면 최대의 길이가 나온다.

이때 최대의 길이가 트리의 지름, 즉 답이 된다.

이 조건을 찾기 위해서는 https://blog.myungwoo.kr/112 이 블로그를 참고하면 좋을 것 같습니다.

 

import sys
sys.setrecursionlimit(10**9)

input= sys.stdin.readline

n = int(input())
n_list=[[] for _ in range(n+1)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    n_list[a].append([b,c])
    n_list[b].append([a,c])

def dfs(x,y):
    for i in n_list[x]:
        p,v = i
        if visited[p]== -1:
            visited[p] = y+v
            dfs(p,y+v)

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

p= visited.index(max(visited))
visited=[-1 for _ in range(n+1)]
visited[p]=0
dfs(p,0)

print(max(visited))

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1967.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리