[백준] 1167번 - 트리의 지름

---

문제 분석

가장 긴 경로를 찾는 방법을 구하는 문제로 다음과 같은 아이디어를 통해 경로를 구하도록 한다.

가장 긴 경로 찾기 아이디어
임의의 노드에서 가장 긴 경로롤 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나이다.

소스 코드

# 트리의 지름

from collections import deque

N = int(input())
A = [[] for _ in range(N + 1)]

for _ in range(N):
    Data = list(map(int, input().split()))
    index = 0
    S = Data[index]
    index += 1
    while True:
        E = Data[index]
        if E == -1:
            break
        V = Data[index + 1]
        A[S].append((E, V))
        index += 2

distance = [0] * (N + 1)
visited = [False] * (N + 1)


def BFS(v):
    queue = deque()
    queue.append(v)
    visited[v] = True
    while queue:
        now_Node = queue.popleft()
        for i in A[now_Node]:
            if not visited[i[0]]:
                visited[i[0]] = True
                queue.append(i[0])
                distance[i[0]] = distance[now_Node] + i[1]


BFS(1)
Max = 1

for i in range(2, N + 1):
    if distance[Max] < distance[i]:
        Max = i

distance = [0] * (N + 1)
visited = [False] * (N + 1)
BFS(Max)
distance.sort()
print(distance[N])

---

처음에 DFS방식으로 해서 시간초과가 난 코드

# 트리의 지름

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

V = int(input())
arr = [[] for _ in range(V + 1)]
visit = [False for _ in range(V + 1)]
Result = 0

for _ in range(V):
    values = list(map(int, input().split()))
    idx = values[0]
    arr[idx] = values[1:-1]


def DFS(idx, result):
    global Result
    visit[idx] = True
    check = False

    for i in range(0, len(arr[idx]), 2):
        node = arr[idx][i]
        if not visit[node]:
            result += arr[idx][i + 1]
            DFS(node, result)
            result -= arr[idx][i + 1]
            check = True
        if not check and i == len(arr[idx]) - 2:
            Result = max(Result, result)

    visit[idx] = False


for i in range(1, V + 1):
    DFS(i, 0)

print(Result)