1967번 - 트리의 지름
해당 문제를 풀 때에 다음을 고려해야합니다.
1. 편향 트리
2. 자식 노드가 2개 이상( + 3개 이상인 케이스 )
해당 트리를 양방향 그래프로 만들어 BFS로 2번하여 푸는 경우가 많았습니다. ( 가장 손쉬운 해결법 )
(루프 노드에서 가장 가중치가 큰 단말 노드 찾고, 해당 단말 노드에서 BFS 최대 가중치 계산)
DFS 1번으로 계산하는 방법은 루프 노드에서 내려가는 단방향 그래프로 만든 후에 가중치를 수시로 갱신하는 방법으로 풀지 않는 이상은 좋은 방법이 없을 듯합니다.
(DFS 1번으로 풀 수 있다고 해서 도전하는데 제법 시간이 걸렸습니다.)
댓글을 작성하려면 로그인해야 합니다.
wak8835 3년 전 2
해당 문제를 풀 때에 다음을 고려해야합니다.
1. 편향 트리
2. 자식 노드가 2개 이상( + 3개 이상인 케이스 )
해당 트리를 양방향 그래프로 만들어 BFS로 2번하여 푸는 경우가 많았습니다. ( 가장 손쉬운 해결법 )
(루프 노드에서 가장 가중치가 큰 단말 노드 찾고, 해당 단말 노드에서 BFS 최대 가중치 계산)
DFS 1번으로 계산하는 방법은 루프 노드에서 내려가는 단방향 그래프로 만든 후에 가중치를 수시로 갱신하는
방법으로 풀지 않는 이상은 좋은 방법이 없을 듯합니다.
(DFS 1번으로 풀 수 있다고 해서 도전하는데 제법 시간이 걸렸습니다.)