[백준] 코딩테스트 문제 풀이 : 1967.트리의 지름 #Tree#DFS
[문제]
일단 문제가 이러쿵 저러쿵 써 있지만 결국 간선의 가중치가 있는 트리에서 리프 노드 - 리프 노드 또는 루트 노드 - 리프 노드 간 가중치의 합 중 큰 값을 출력하는 문제이다.
[접근 방법]
사실, 이게 가중치 없는 트리였으면 이렇게 헤매지는 않았을 것인데, 여튼 가중치가 있으면서 한 번 꼬이고, n이 최대 10000개라는 점을 간과하고 아름답게 재귀로 풀었다가 stacksizeexeed error를 받았다.
(아니 이 놈의 재귀는 그럼 언제 쓸 수 있냐 칵 퉤)
여튼 그래서 n이 일단 10000개이다 그러면 재귀로 푸는 걸 포기한다는 것을 다시 한 번 마음에 새기고, 재귀 호출을 while문으로 변경하면서 약간 DFS와 비슷한 알고리즘으로 문제를 풀었다.
일단 자식이 하나 있는 경우와 두 개 이상인 경우를 나눠서 2개 이상일 때는 리프 노드 간 최장 길이를 계산해주는 것이고 그게 아니라면 자식 노드들 중 가장 가중치가 높은 값을 return해주는 것이고
만약 자식이 없다면 내 자신의 가중치를 리턴하는 방식이다.
재귀에서 stack을 활용하는 DFS로 바꾸면서 해당 노드까지 올 때의 얻을 수 있는 가중치의 최대 합을 저장해주기 위한 스택 배열을 하나 더 생성해주고, 만약 자식 노드가 아직 계산되지 않았다면 stack2에 자식 노드를
다 넣고 다시 리프 노드의 가중치부터 계산해준다. 이 때 부모 노드를 splice나 unshift()로 넣으면 시간 초과가 나므로 count 변수를 써서 일단 자식 노드 중 하나라도 가중치 계산이 안 된 경우에 자식 노드
가중치 계산 이후 부모 노드 가중치를 계산해줘야 하므로 먼저 stack2에 넣어준다.
이런 식으로 stack2에 모든 원소가 없을 때까지 반복문을 돌려주면 stack에는 루트 노드부터 각 리프노드까지의 가중치 값들이 담겨 있고 여기서 max와(루트 - 리프노드), longest에 저장되어 있는 리프 노드 - 리프 노드 간 최장 값을 비교해서 더 큰 값을 출력해주면 문제를 해결할 수 있다.