두 노드간의 최단or최장거리 찾기

과제를 하면서 알게된 방법을 적어보려고 한다

 

과제는 트리의 단말노드 <-> 단말노드 사이의 가중치 합에 대한 최댓값을 구하는 문제인데

처음에는 백준에서 풀었었던 트리의 지름(1967번, 1167번) 이 기억나서 

dfs 2번의 과정이면 충분히 해결할 수 있을거라고 생각하고 문제를 접근했다.

결과는 WA

 

트리의 지름의 경우 "임의의 노드"를 기준으로 하기 때문에 

단말노드와 단말노드 간의 거리를 구하기 위해 내부코드만 살짝 바꿔주었는데

뭔가 반례가 있나보다

단말노드 간의 정확한 계산은 dfs 을 2번 거치는 트리의지름 방법으로는 해결할 수 없다.

 

단말노드간의 정확한 계산방법을 풀이한다

계산방법은 "후위순회의 접근방법을 통한 자식을 관찰?하는 방법" 이다

후위 순회는 좌->우 자식을 전부 확인하고 자신을 확인하는 순회법이다

좌, 우 자식의 반환값을 통해 현재 노드의 정보를 갱신해가는 방법으로 해결할 수 있다.

 

다음의 트리를 기준으로 최댓값을 찾아보자

 

루트노드인 -15의 가중치를 가진 노드부터 시작해서

후위순회하듯이 좌측, 우측 자식의 반환값을 받을 것이다

반환값의 형태는 ( a, b ) 의 2개의 값을 가지는 한 쌍이다

 

( a, b ) 의 형태에서

a 는 두 자식중에서 큰 가중치를 골라 현재 가중치와 더하는

즉 현재노드의 자식에 위치한 단말노드까지의 최댓값을 의미하고

b 는 두 자식의 가중치와 현재 가중치를 모두 더하는

즉 현재노드의 자식에 위한 단말노드 간의 최댓값을 의미한다

 

좀더 간단하게 말하자면

a는 현재노드부터 좌/우 자식중 가장 큰 가중치를 갖는 경로,

b는 a를 통해 좌, 우자식을 둘다 연결하는 => 단말노드와 단말노드 간의 최댓값 경로가 된다

 

이 방법을 이용하여 -8 의 가중치를 갖는 노드의 리턴값을 예를 들면 다음과 같다

단말노드는 자식자체가 없기 때문에 가중치값을 쌍으로 반환하게 된다

비교대상은 항상 a(좌측) 값으로 이루어진다

2, 6 중에서 6이 크므로 -8과 더해서 a:-2 이라는 값이 만들어지고,

2, 6, -8을 더한 b:0 이라는 값이 만들어진다

이떄 -2는 -8 노드 기준 우측자식의 단말노드부터 현재노드까지의 최댓값을 의미하고

0은 -8 노드 기준 좌/우측 자식의 단말노드부터 현재노드까지의 최댓값을 의미하게 된다

 

이런식으로 재귀를 통해 다음과 같은 결과를 얻을 수 있다.

최댓값에 대한 비교는 항상 b로 이루어지고, 다음 결과를 통해 27이 정답이 됨을 알 수 있다