1967 트리의 지름 python

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

1967번: 트리의 지름

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

생각해내는데 오래걸리는 문제였다.

두 노드사이의 거리가 가장 멀리있는 노드 둘을 찾아서 가중치의 합을 출력해야한다.

가장 멀리있는 노드 두개를 찾는 방법은 이렇게 하면 된다.

1. 1번노드에서 가장 멀리있는 노드(n1)를 찾는다.

2. n1에서 가장 멀리있는 노드를 찾는다.

 

이렇게하면 가장 멀리있는 두 노드를 찾을 수 있다.

dfs를 2번만 사용하면 된다는 것.

모든 노드에 대해 dfs를 하면 시간초과로 틀린다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

import sys
input = sys.stdin.readline

"""
1번에서 가장 멀리있는 점을 시작점으로 정함
시작점을 기준으로 DFS.
가중치 총 합 출력

"""

n = int(input())
tree = [[] for i in range(n+1)]
for i in range(n-1):
    start, end, weight = map(int,input().split())
    tree[start].append((end, weight))
    tree[end].append((start, weight))

ans = 0

def dfs(start):
    global ans
    visited = [False] * (n+1)
    visited[start] = True
    sum_w = [0] * (n+1)
    list = [start]
    while list:
        s = list.pop()
        for e, w in tree[s]:
            if not visited[e]:
                visited[e] = True
                list.append(e)
                sum_w[e] = sum_w[s] + w
                
    ans = max(sum_w)
    return sum_w.index(ans)

dfs(dfs(1))
print(ans)

33828

60