[programmers][월간 코드 챌린지 시즌1] 트리 트리오 중간값

문제 : programmers.co.kr/learn/courses/30/lessons/68937

---

트리의 지름을 구하는 문제의 심화과정.

임의의 노드(let, v1)에서 dfs를 한 번 돌려서 가장 먼 노드(let, v2)를 구한다. (첫번째 BFS)

v2 노드에서 가장 먼 노드들을 구한다.

(두번째 BFS) 이 때 구한 가장 먼 노드들과 v2 노드의 거리가 트리의 지름이 된다. 만약 가장 먼 노드들이 복수 개(let, d1, d2)라면 f(v2, d1, d2)를 선택하면 이들의 중앙값은 트리의 지름이 되므로 정답은 트리의 지름이 된다.

v2 노드에서 가장 먼 노드(let, v3)가 한 개라면 한 번 더 BFS를 돌려야한다. 

[그림 1]

왜냐하면 v2를 지름의 끝으로 트리의 지름을 만드는 노드들을 구했을 때는 v3 노드만 찾을 수 있었지만 [그림1] 과 같이 v3을 지름의 끝으로 했을 때는 v2와 다른 서브트리에 있는 트리의 지름을 만들 수 있는 노드를 찾을 수 있기 때문이다.

따라서 v3를 끝 지점으로 다시 한 번 지름을 만들 수 있는 노드들을 검색할 필요가 있다.

v3 노드에서 가장 먼 노드들을 구했을 때 여러개가 있다면 마찬가지로 트리의 지름이 정답이 된다.

만약 가장 먼 노드가 한 개(let, v4)라면 v3 노드로 트리의 지름을 만드는 노드들 중 v3 노드와 가장 인접한 노드(let, v5)를 선택한다.

즉, v3과 v5의 거리차는 1이다.

f(v3, v4, v5)가 f의 제일 큰 값이 된다. 각 노드 간 거리를 오름차순 정렬하면, [v3~v5 = 1, v4~v5 = 트리의 지름 - 1, v3~v4 = 트리의 지름.] 이 되고 이들 중 중앙 값인 트리의 지름 - 1이 정답이 된다.

 

시간복잡도는 O(3E).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%9B%94%EA%B0%84%20%EC%BD%94%EB%93%9C%20%EC%B1%8C%EB%A6%B0%EC%A7%80%20%EC%8B%9C%EC%A6%8C1/%ED%8A%B8%EB%A6%AC%20%ED%8A%B8%EB%A6%AC%EC%98%A4%20%EC%A4%91%EA%B0%84%EA%B0%92.cpp

---

해설을 참고해서 풀었다.

트리의 지름 읽어보기만 하고 풀어보는건 처음인데 새로운 문제를 풀어보는 건 재밌구나.

아 배울거 많다. 즐겁다.