wak8835   3달 전

해당 문제를 풀 때에 다음을 고려해야합니다.

1. 편향 트리

2. 자식 노드가 2개 이상( + 3개 이상인 케이스 )

해당 트리를 양방향 그래프로 만들어 BFS로 2번하여 푸는 경우가 많았습니다. ( 가장 손쉬운 해결법 )

(루프 노드에서 가장 가중치가 큰 단말 노드 찾고, 해당 단말 노드에서 BFS 최대 가중치 계산)

DFS 1번으로 계산하는 방법은 루프 노드에서 내려가는 단방향 그래프로 만든 후에 가중치를 수시로 갱신하는 
방법으로 풀지 않는 이상은 좋은 방법이 없을 듯합니다.

(DFS 1번으로 풀 수 있다고 해서 도전하는데 제법 시간이 걸렸습니다.)

댓글을 작성하려면 로그인해야 합니다.