[백준 1967 파이썬] 트리의 지름 (골드 4, 트리)

알고리즘 유형 : 트리, BFS, DFS
풀이 참고 없이 스스로 풀었나요? : △

https://www.acmicpc.net/problem/1967

소스 코드(파이썬)

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

n = int(input())
tree = [[] for _ in range(n+1)]
# 양방향 연결 리스트로 저장
# 루트 노드 1인 부모-자식 트리라 하더라도
# 루트의 지름을 구하려면 임의의 노드에서
# 부모-자식 상하 관계에 구애받지 않고
# 모든 노드를 순회할 수 있어야하기때문.
for _ in range(n-1):
    parent, child, weight = map(int, input().split())
    tree[parent].append((child, weight))
    tree[child].append((parent, weight))
    
def DFS(node, cost):
    for adj_node, adj_w in tree[node]:
        cal_w = cost + adj_w
        if visited[adj_node] == -1:
            visited[adj_node] = cal_w
            DFS(adj_node, cal_w)
    
    return

# 첫 번째 DFS로 지름의 양 끝점 중 하나 구하기(성질 증명은 검색)
visited = [-1]*(n+1)
visited[1] = 0

DFS(1, 0)
idx, tmp = 0, 0
for i in range(1, len(visited)):
    if visited[i] > tmp:
        tmp = visited[i]
        idx = i

# 두 번째 DFS로 나머지 트리의 지름 끝점 하나를 찾고 지름 구하기
visited = [-1]*(n+1)
visited[idx] = 0
DFS(idx, 0)

print(max(visited))
        

풀이 요약

1. 1167 트리의 지름 문제랑 똑같은 문제이다. 풀이는 이 링크에서 확인하자.

   한 가지 설명하자면, 문제에서 루트 노드가 존재하는 부모-자식 관계 트리를 주었다. 우리는 이 트리를 저장할 때, 양방향 그래프로 저장하여야 한다. 지름을 구하기 위해서는 임의의 노드에서 그래프의 모든 노드로 접근할 수 있어야하기 때문이다.

배운 점, 어려웠던 점

• 1167 문제와 똑같았는데, 파이썬에서 재귀 깊이 한도 기본값이 1000임을 깜빡해서 재귀 깊이를 넓혀주지 않아 런타임 에러가 났다.