일단 N개의 정점과 N-1개의 간선이 있다는 것은 주어진 그래프는 트리라는 것이다.원래 문제로부터 약간만 변형시켜 보자. 최소 시간을 찾는 것이 아닌, 어떤 시간 T가 주어졌을 때 돈을 적절히 써서 가장 오래 걸리는 도시까지의 시간을 <=T 로 만들 수 있는지 판단하는 문제로 변형시켜보자.
도시 1을 루트 노드라고 하고 다음과 같은 배열을 정의하자.
p 를 u의 부모 노드라고 했을 때, H[u] 는 p에서 시작, 간선 {p,u} 를 지나서 가장 오래 걸리는 도시까지 가는데 걸리는 시간으로 정의하자.
가장 오래 걸리는 도시는 당연히 단말 노드 중 하나이니, 위 배열 값은 깊이 우선 탐색으로 쉽게 구할 수 있다.
그렇다면 다음 문제를 보자.
루트가 p라고 했을 때, 루트의 자식 노드 u에서 H[u]>T 라면 어떻게 해야 할까? 당연히 간선 {p,u}의 가중치를 H[u]가 T보다 작거나 같아질 때까지 돈을 써야 한다. 이게 최선의 선택이라는 건 자명한다.
이때 H[u]<=T 가 가능하다면 u 의 자식 노드들은 더 이상 방문할 필요가 없게 된다.
만약 {p,u} 의 가중치를 최대한 낮춰도 H[u] 의 값이 T보다 크다면? 간선 {p,u} 는 가중치를 낮출 만큼 낮췄으니 더 이상 할 수 있는 게 없다. 그렇다면 u의 자식 노드 v로 넘어가, 위와 똑 같은 방법으로 {u,v}의 간선의 가중치를 낮춰야 한다. 이런 식으로 그리디 하게 간선의 가중치를 낮추는 게 최선의 방법이라는 건 직관적으로 쉽게 알 수가 있다.
위 알고리즘 또한 깊이 우선 탐색으로 구현할 수 있다.
다시 원래 문제로 돌아와 보자. 우리는 이 T를 최소화 하고 싶다. 어떻게 할까?
이분 검색을 쓰면 된다. 어떤 임의의 T에 위 알고리즘이 “불가능하다” 라는 결과를 리턴한다면 T보다 작은 값은 고려해 볼 필요가 없다. 그 반대로 “가능하다” 를 리턴하면 T보다 큰 값은 고려해 볼 필요가 없다.
깊이 우선 탐색이 O(V+E) 고 이분 검색이 O(lg N) 이니, 위 알고리즘 시간 복잡도는 최악의 경우 O((2N-1)lg K) 정도가 될 것이다. 충분히 1초 내에 들어온다.
출처:likepad