[BOJ/백준] 14657 준오는 최종인재야!

import math
import sys


def dfs(node):
    stack = [(node,0,0)]
    visited = [True]*(N+1)
    distance = 0
    max_node = -1
    min_time = float('inf')
    visited[node] = False
    while stack:
        node,dis,time = stack.pop()
        if dis > distance:
            distance = dis
            max_node = node
            min_time = time
        elif dis == distance and min_time > time:
            max_node = node
            min_time = time

        for next_node in graph[node]:
            if visited[next_node]:
                new_dis = dis + 1
                new_time = time + graph[node][next_node]
                visited[next_node] = False
                stack.append((next_node,new_dis,new_time))

    return [max_node,distance,min_time]



input = sys.stdin.readline

N,T = map(int,input().split())


graph = [{} for _ in range(N+1)]


for _ in range(N-1):
    x,y,time = map(int,input().split())
    graph[x][y] = time
    graph[y][x] = time

far_node_info = dfs(1)

result = dfs(far_node_info[0])


print(math.ceil(result[2]/T))

트리의 지름 이 문제를 풀어보면 해당 문제를 좀 더 쉽게 풀 수 있다.

문제의 조건은 총 2가지이다. 문제를 가장 많이 풀어야하며, 그 푸는데 시간이 가장 짧아야한다.

이 문제는 트리구조이다. 그래서 문제를 가장 많이 푼다는 것은 트리의 지름을 구하는것과 같다.

그러므로 처음 dfs로 아무 노드에서 가장 먼 노드를 찾고, 그 노드에서 가장 먼 노드들을 찾으면 그게 트리의 지름이 된다.

이걸 응용해서, 첫 dfs로 가장 먼 노드 하나를 찾는다.

그리고 두번째 dfs로 찾은 가장 먼 노드를 기준으로, dfs를 돌려서 깊이가 가장 깊은 노드들을 찾는다. 그리고 그 중에서, 시간이 가장 짧은 것을 선택해주면 된다.

이 문제는 1967번 문제의 트리의 지름을 응용한 문제이고, 트리의 특성에 대해 알고 있으면 쉽게 풀 수 있었던 문제였지만,

처음에 트리의 지름에 대한 아이디어를 얻지 못해서 어려웠던 문제이다.