boj.kr/1967 트리의 지름 (gold4) 파이썬 풀이

1. 그래프 행렬 초기화

2. 인접한 노드에 대해 순환호출하되 거리 누적해 전달하는 dfs 함수 정의

3. 인접행렬 순회하면서 dfs 호출하고 최대 거리 저장

4. 최대 거리 리스트에서 최댓값 출력

 

 

문제에 제시된 테스트 케이스는 통과했으나 제출 시 메모리 초과했다.

import sys
sys.setrecursionlimit(10**6)

input = sys.stdin.readline

N = int(input())
adj = [list(map(int, input().split())) for _ in range(N-1)]
graph = [[0] * N for _ in range(N)]

for (y, x, d) in adj:
    graph[y-1][x-1] = d
    graph[x-1][y-1] = d

def dfs(cur, nxt, d):
    global max_d
    max_d = d if max_d < d else max_d
    for node in range(N):
        if graph[nxt][node] != 0 and not cur == node: # and not visited[nxt][node]
            nd = d + graph[nxt][node]
            dfs(nxt, node, nd)

max_d = -1e9
max_d_list = set()
for (c, n, d) in adj:
    dfs(c-1, n-1, d)
    max_d_list.add(max_d)
    max_d = -1e9

    dfs(n-1, c-1, d)
    max_d_list.add(max_d)
    max_d = -1e9

print(max(max_d_list))

 

 

정답 풀이

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

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

for _ in range(N-1):
    (s, e, d) = list(map(int, input().split()))
    graph[s].append([e, d])
    graph[e].append([s, d])

def dfs(cur, d):
    for (nxt, nd) in graph[cur]:
        if visited[nxt] == -1:
            visited[nxt] = d + nd
            dfs(nxt, 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))

그래프 인덱스를 트리의 노드 번호로 사용한다.

트리의 루트로부터 가장 먼거리에 있는 노드로부터 가장 먼 거리에 있는 노드까지의 거리가 트리의 지름이다.