boj.kr/1167 트리의 지름 (gold2) 파이썬 풀이

1. 인덱스를 노드 번호로 갖고 연결 노드와 그 거리쌍을 요소로 갖는 그래프를 초기화

2. 인덱스를 노드 번호로 갖고 요소를 누적 거리값으로 갖는 방문체크 배열을 -1으로 초기화

3. 노드 번호와 누적 거리값을 인자로 받고 연결 노드를 탐색하는 dfs 함수 정의

4. 트리의 루트 노드에서 가장 먼 거리에 있는 노드번호 찾기

5. 4번에서 찾은 노드로부터 dfs 결과 누적거리값 중 최대값을 출력

 

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

N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N):
    I = list(map(int, input().split()))
    s, e = 1, 3
    while e < len(I):
        graph[I[0]].append(I[s:e])
        s += 2
        e += 2

def dfs(node, d):
    for (ne, nd) in graph[node]:
        if visited[ne] == -1:
            visited[ne] = d + nd
            dfs(ne, d + nd)

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

visited = [-1] * (N+1)
visited[start] = 0
dfs(start, 0)
print(max(visited))

 

노드사이 거리값을 고려해야 하는 dfs 문제에서 인덱스를 노드 번호로 갖는 graph를 사용하면 메모리를 절약할 수 있다.

트리의 지름은 루트 노드에서 가장 먼 거리에 있는 노드의 dfs 결과 최대 누적거리값이다.