목차
트리의 지름
- 참고
- 먼저 관련된 텀들을 정리해보자
- 트리뿐 아니라 일반 그래프에서도 똑같이 정의되는 텀들이다.
- 노드 v의 이심률(eccentricity of v): v와 다른 노드들 까지의 거리중 가장 긴 거리. (=v에서 가장 멀리 떨어진 노드까지의 거리)
- 그래프가 연결그래프가 아닌 경우에는, 모든 노드의 이심률이 무한대로 정의된다
- 그래프의 지름(graph diameter): 이심률의 최댓값 (= 이심률이 최대인 노드에서의 이심률)
- 그래프에서 가장 멀리 떨어져 있는 두 노드 사이의 거리
- 그래프의 반지름(graph radius): 이심률의 최솟값 (= 이심률이 최소인 노드에서의 이심률)
- 그래프의 중심에서 가장 멀리 떨어진 노드까지의 거리
- 그래프의 중심 (center of graph): 이심률이 그래프의 반지름과 같은 노드들
- 가장 멀리 떨어진 노드까지의 거리가 최소인 노드들
- 그래프는 중심을 여러개 가질수도 있다.
- 센트로이드(Centroid)와는 다른 개념이다!
트리에서의 성질
- 트리에서는 다음과 같은 성질들이 성립한다 (트리의 가중치는 음수가 아니라고 가정)
- 트리에서 가장 긴 단순 경로의 길이 = 가장 멀리 떨어진 두 노드 간의 거리 = 트리의 지름
- 트리의 중심은 1개 또는 2개
- 가중치 없는 트리의 경우, 지름이 d이면 반지름은 ceil(d/2)
- u→v 가 트리에서 가장 긴 단순 경로일때, 어떤 노드에서 가장 멀리 떨어진 노드는 u 또는 v 이다. (그 외에도 더 있을수는 있다)
- 트리에서 가장 긴 단순 경로가 여러개인 경우, 그것들은 모두 트리의 중심을 지난다.
- 트리의 중심이 2개이면, 그 두 개를 모두 지난다. 정확히는 그 두 중심 노드를 잇는 엣지를 지난다.
- 등등
- 대충 생각해보면 쉽게 떠올릴 수 있는 내용들이긴 하다. 하지만 대충 생각해볼 필요도 없이 그냥 바로바로 나오도록 기억해두는게 좋다. 증명은 위의 링크들을 참고.
트리의 지름을 구하기
- O(N)에 계산할 수 있는 방법이 두 가지 있다.
- 1) 위의 성질을 이용해서 두번의 DFS로 구하는 방법.
- 2) 트리에서의 DP를 이용해서 구하는 방법.
- 일반적으로는 두번의 DFS 로 구하는 방법이 빠르고 간단하다
- 어떤 노드에서 가장 멀리 떨어진 노드는, 트리의 지름을 이루는 양 끝 노드들 중 하나이다 라는 성질을 이용하면 알고리즘은 쉽게 나온다
- 알고리즘은
- 1. 임의의 노드에서 DFS를 돌려서 가장 멀리 떨어진 노드 a를 찾는다. ⇒ a는 트리의 지름의 한쪽 끝이 된다
- 2. a에서 DFS를 돌려서 가장 멀리 떨어진 노드 b를 찾는다. ⇒ b는 트리의 지름의 다른쪽 끝이다.
- 3. dist(a,b)가 트리의 지름이 된다(!)
- 이 방식을 사용하면 트리의 지름의 양 끝점(=가장 멀리 떨어진 노드쌍)이나, 트리의 지름에 대응되는 경로(=가장 긴 단순 경로)도 함께 얻을수 있다.
- 특정한 경우에는 tree dp를 써서 구하는 것이 좀 더 나은 경우도 있기는 하다
- 음수 가중치를 갖는 트리의 경우
- 트리의 지름 (가장 긴 단순 경로의 길이) 뿐 아니라, 가장 긴 단순 경로의 개수까지 구하고 싶은 경우
- 이 방법은 뒤쪽에 따로 설명
어떤 노드의 이심률과 그 노드로부터 가장 거리가 먼 노드를 구하기
- u의 이심률은 u에서 가장 멀리 떨어져있는 노드까지의 거리이다. (위에도 적었지만, 잘 안쓰는 용어이다보니 까먹을까 봐 다시 한번 적는다)
- 모든 노드의 이심률과 가장 거리가 먼 노드를 O(n)에 구할 수 있다.
- 트리의 지름을 찾을 때 사용한 성질인, 어떤 노드에서 가장 멀리 떨어진 노드는, 트리의 지름을 이루는 양 끝 노드들 중 하나이다를 이용하면 방법은 직관적으로 나온다.
- 트리의 지름을 찾고 → 트리의 지름을 이루는 양 끝 노드 u, v로부터 각각 DFS를 돌려서 각 노드까지의 거리를 구해둔다.
- dist(u, X)는 트리의 지름을 계산하는 과정에서 이미 구했을 것이므로, dist(v, X)만 추가로 구하면 된다
- 어떤 노드 w에서 가장 먼 노드는, dist(u, w)과 dist(v, w) 중 값이 큰 쪽에 해당되는 노드이다.
- 시간복잡도는 여전히 O(n)이다. 총 3번의 DFS가 필요하다.
- 식을 조금 바꿔서 정리하면, w의 이심률은 {w에서 중심까지의 거리} + {반지름} 이 된다고도 쓸 수 있다.
- max_u(dist(w, u)) = dist(w, center) + radius
- 관련 문제
13016 : 모든 노드의 이심률을 출력하는 문제
트리의 중심과 반지름을 구하기
- O(n)에 구할 수 있다.
- 단순하게는, 위의 방식대로 모든 노드의 이심률을 구한 뒤에, 이심률이 최소인 노드를 구하면 중심과 반지름을 찾을수 있다.
- 하지만 모든 노드의 이심률을 구하기 위해서는 트리의 지름을 구하는 과정에서 계산한 dist(u, X) 이외에도 추가로 DFS를 한번 더 돌려서 dist(v, X)를 구해야 하는데, 트리의 중심만을 구하기 위해서는 굳이 그럴 필요가 없다.
- 트리의 중심은 가장 긴 단순 경로 안에 포함되므로, 여기에 해당되는 노드들에 대해서만 이심률을 구해주면 되는데, 이러한 노드들에 대해서는 dist(v, X) = {지름} - dist(u, X) 이므로, dist(v, X)를 따로 구할 필요가 없다.
- 즉, u→v 경로에 있는 노드들 중에서, max(dist(u, X), dist(u, v) - dist(u, X)) 를 최소로 하는 X가 트리의 중심이 된다.
- 만약 가중치가 없는 트리라면 이 계산이 더욱 간단해진다. 트리의 반지름은 ceil(d/2) 이 되고, 중심은 u→v 경로에서 가장 가운데에 위치하는 (d/2번째) 노드가 된다.
- 시간복잡도는 O(n). 2번의 DFS로 계산 가능하다.
- 관련 문제
Time To Live 가중치 없는 트리에서 반지름 구하기- 스크루지 민호 가중치 없는 트리에서 반지름 구하기
Go Go Gorelians 가중치 없는 트리에서 중심 구하기. n⇐1000 이라서 O(n^2) 풀이도 돌아간다.
기타 활용 문제
음수 가중치를 갖는 트리에서의 지름
- 위의 성질이 안먹히므로, dfs를 이용해서 구하는 방법은 쓸수 없다.
- 하지만 트리 DP를 사용해서 구할수 있다
- (사실 음수 가중치가 있는 트리에서 지름을 구하라는 문제를 접한적이 없다)
동적 트리에서의 지름
노드가 계속 추가되는 경우- 오프라인 쿼리 형태로 미리 모든 노드가 추가된 이후의 트리를 알수 있다면, 빠르게 처리가 가능하다.
- 트리의 지름과 더불어서 트리의 지름을 이루는 양 끝 노드를 유지하고 있으면서, 노드가 하나씩 추가될때마다 이 값을 갱신한다.
- 현재 트리에서의 지름이 d이고 양 끝 노드가 u,v 일때, 트리에 w라는 노드와 엣지가 추가되는 경우를 생각하자.
- w에서 가장 먼 노드까지의 거리는 d' = max(dist(u, w), dist(v, w))이다.
- 만약 d'>d 이면, 지름을 d'으로 갱신하고, 지름을 이루는 양 끝 노드 역시 갱신해주면 된다.
- dist(u, w)와 dist(v, w)을 구하는 것은, 경로의 길이의 방법을 이용하면 O(nlogn)의 전처리 이후에 O(logn)에 가능하다. 즉, 노드 한개 추가할 때마다 O(logn)의 시간복잡도로 지름을 갱신해줄수 있다.
- 관련 문제:
