1167 - 트리의 지름 / gold 2 / DFS, 트리 지름

- 시간초과

- leaf_node들을 모두 dfs 실행 

"""
1167 - 트리의 지름 / gold 2
"""
import sys

input = sys.stdin.readline

# 정점 개수 입력 받기
v = int(input())

# 트리 정보 입력 받기
graph = [[] for _ in range(v + 1)]
for _ in range(v):
    info = list(map(int, input().split()))
    for i in range(1, len(info) - 1, 2):
        graph[info[0]].append((info[i], info[i + 1]))

leaf = []
for n in range(1, v + 1):
    if len(graph[n]) == 1:
        leaf.append(n)


def dfs(now_dist, now_node, visited):
    if visited[now_node] == -1:
        visited[now_node] = now_dist
        for next_node, next_dist in graph[now_node]:
            dfs(now_dist + next_dist, next_node, visited)


all_res = 0
for node in leaf:
    visited = [-1] * (v + 1)
    dfs(0, node, visited)
    res = max(visited)
    if res > all_res:
        all_res = res
print(all_res)

 

- 정답

"""
1167 - 트리의 지름 / gold 2 / DFS, 트리지름
"""
import sys

input = sys.stdin.readline

# 정점 개수 입력 받기
v = int(input())

# 트리 정보 입력 받기
graph = [[] for _ in range(v + 1)]
for _ in range(v):
    info = list(map(int, input().split()))
    for i in range(1, len(info) - 1, 2):
        graph[info[0]].append((info[i], info[i + 1]))

leaf = []
for n in range(1, v + 1):
    if len(graph[n]) == 1:
        leaf.append(n)


def dfs(now_dist, now_node, visited):
    if visited[now_node] == -1:
        visited[now_node] = now_dist
        for next_node, next_dist in graph[now_node]:
            dfs(now_dist + next_dist, next_node, visited)


visited = [-1] * (v + 1)
dfs(0, 1, visited)
node = visited.index(max(visited))

visited = [-1] * (v + 1)
dfs(0, node, visited)
print(max(visited))

 

핵심 개념 알기

- 임의의 노드(ex- 1번 노드)와 가장 긴 지름을 이루는 노드(ex- ??번 노드)는

트리의 가장 긴 지름에서의 한 노드이다. 

 

피드백

- 핵심 개념의 알고리즘을 몰라 leaf 노드들을 전부 dfs로 돌려 시간 초과

- 이렇게 하면 시간 초과 날 것을 알았지만 구현 후, 검색 시도했슴다