백준 1967번 : 트리의 지름

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

1967번: 트리의 지름

전형적이진 않지만 조금만 생각하면 풀 수 있는 그래프 탐색 문제이다.

 

N개의 노드로 구성된 트리가 주어지고 간선으로 연결된 두 노드의 번호와 간선의 길이(비용)가 주어진다. 간선의 개수는 N-1개로 일정하다. 이 때 이 트리를 이루는 임의의 두 노드 사이의 거리의 최댓값을 구하는 문제다. 

 

각 노드에 대하여 다른 노드로 가는 비용을 모두 더하여 값을 저장하고 그 값들 중에 최댓인 값을 구하면 되겠지만, 노드의 개수는 최대 10,000개 이므로 O(N^2) 시간 복잡도를 가질 경우 시간초과 판정을 받을 수 있다.

 

처음엔 그리디로 접근했다. 입력으로 들어오는 간선을 길이(비용) 기준으로 오름차순 정렬하여 길이가 긴 간선부터 순서대로 더해줬다. 하지만 길이가 비교적 작은 간선들이 연결될 경우 길이가 긴 간선보다 길어질 수 있다는 반례가 존재했다. 그래서 다른 풀이를 생각했다.

 

개념적으로 접근해보자. 트리 안의 두 노드를 선택해서 그 사이 간선들의 길이가 최대한 길어지기 위해서는 자식이 없는 노드(리프 노드)에서 또 다른 리프 노드로 연결되는 것이 최선이다. 왜냐하면 만약 선택한 노드가 자식을 갖고 있을 경우 그 노드와 자식 사이의 간선 길이를 계산하여 더 길어질 수 있는 여지가 있기 때문이다.

 

먼저 재귀로 구현한 DFS를 통해 루트 노드부터 리프 노드까지 모든 노드들을 방문한다. 그리고 각 노드들은 자신이 루트인 서브 트리에서 리프 노드까지 연결되는 간선 길이의 총합을 저장한다. 자식 노드가 여러 개일 경우 그 값들 중 최댓값을 부모 노드에 전달하고 모든 노드를 탐색한 후 저장된 값을 이용해 답을 구한다.

 

노드에 저장된 값이 2개 이상일 때, 가장 큰 2개를 더 한 값이 그 노드를 거치면서 2개의 리프 노드가 연결된 간선의 길이다. 이렇게 계산된 값들 중 최댓값을 찾아서 출력하면 정답이 된다.

 

※ 최악의 경우 최대 재귀 깊이가 10,000이 넘기 때문에 최대 깊이 설정을 해주어야 오류가 없다.

 

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

def dfs(x):
    m = 0
    for i, j in s[x]:
        d[x].append(j + dfs(i))
        m = max(m, d[x][-1])
    return m

n = int(input())
s = [[] for _ in range(n+1)]
d = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b, e = map(int, input().split())
    s[a].append((b, e))
dfs(1)

r = 0
for i in d:
    i.sort(reverse=True)
    r = max(r, sum(i[:2]))
print(r)