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

문제

백준 - 11725번: 트리의 부모 찾기

분석

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 문제이다.

이 문제는 입력 형식이 불친절한 문제였다.
5 # 먼저 노드 개수가 주어지고,
1 3 2 -1 # 맨 앞은 노드번호, 그 다음 두 개씩 끊어서 연결된 노드와 그 노드까지 거리를 반복해서 줬다.
2 4 4 -1 # -1은 줄의 마지막을 표시한다.
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1

트리의 지름을 구하는 방법은 DFS를 두 번 사용하면 해결할 수 있다.
먼저 아무 정점에서 DFS를 시작해서 그 노드로 부터 가장 먼 노드를 구한다.
그 다음, 구한 노드로 부터 DFS를 진행하여 가장 먼 거리를 구하면 된다.
이때, 가장 먼 노드와, 그 값을 global로 두고 잘 갱신한다.
두 번째 dfs를 진행하기 전에 visited 배열을 다시 초기화주는 것도 잊지 말고 해야한다.

n이 100000이므로 재귀 최대 깊이를 10^5+1로 늘려준다.

코드

해결언어 : Python

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

v = int(input())
tree = [[] for _ in range(v+1)]
for _ in range(v):
    info = list(map(int, input().split()))
    node = info[0]
    for i in range(1, len(info)-1, 2):
        to, d = info[i], info[i+1]
        tree[node].append((to, d))
    
def dfs(x, dist):
    global mx, mx_node
    if mx < dist:
        mx = dist
        mx_node = x
    visited[x] = True
    for nx, d in tree[x]:
        if not visited[nx]:
            dfs(nx, dist+d)

visited = [False]*(v+1)
mx, mx_node = -1, -1
dfs(1, 0)
visited = [False]*(v+1)
dfs(mx_node, 0)
print(mx)

끝으로..

매일 문제 하나, TIL 하나는 꾸준히 작성하겠다는 마음으로..!