BOJ 1967(트리의 지름)풀이

solved.ac 티어 : 골드 4

www.acmicpc.net/problem/1967

1967번: 트리의 지름

이문제는 의외로 간단한데 어떤 노드에서 와 연결된 노드들 중에 재일 마지막 노드까지의 거리가 첫 번째로 큰 값과 두 번째로 큰 값의 합이 그 노드를 포함했을 때 가장 긴 길이이다. 이걸 dfs으로 탐색하면서 노드별로 가장 긴 길이 중에서도 가장 긴 길이를 출력하면 된다

(백준 1967의 예시 그림)

. 예시로 봤을 때 4번 노드를 포함하는 최대 길이는 8이다. 4의 자식 노드를 포함하는 가장 긴 길이가 1과 7이므로 가장 큰 값 7, 다음으로 큰 값 1을 더하면 4번 노드를 포함하는 최대 길이가 된다. 이거를 모든 노드에 다해주면 된다. 3번 노드 같은 경우는 5번과 6번 자식 노드가 있는데 5번 노드는 최대길이가 19이고 6의 최대 길이는 16이다. 하지만 이 둘을 다하고 11과 9를 또 더하면 구간의 값을 모두 더하는 게 돼버린다. 이때 값을 return 해서 위로 보내줄 때는 자신의 자식 노드가 연결된 길이의 최댓값을 위로 올려주면 된다. 그러면 3번 노드에는 15+11과 10+9가 있으니 11+15+10+9=45 값을 저장하고 리턴은 25를 해주면 된다. 탐색을 마치고 저장한 값들 중 가장 큰 값을 출력하면 된다.

import sys
sys.setrecursionlimit(10**9)
def f(x):
    #print("#",x)
    global ma,sta
    st=[0,0]
    for i in range(len(graph[x])):
        if sta[graph[x][i][0]]==0:
            #sta[graph[x][i][0]]=1
            q=f(graph[x][i][0])+graph[x][i][1]
            if q>st[0]:st=[q,st[0]]
            elif q>st[1]:st=[st[0],q]
    ma=max(ma,st[0]+st[1])
    #print("##",ma,st)
    return st[0]
input=sys.stdin.readline
a=int(input())
sta=[0]*(a+1)
graph=[[]for i in range(a+1)]
for i in range(a):
    l=list(map(int,input().split()))
    for i in range(1,len(l)-1,2):
        graph[l[0]].append([l[i],l[i+1]])
print(graph)
ma=0
f(1)
print(ma)