본문 바로가기

트리의 지름

BOJ)13016 내 왼손에는 흑염룡이 잠들어 있다 문제: icpc.me/13016 오랜만에 문제 포스팅을 한다. 문제를 요약하면 한 정점 v에서 다른 정점으로의 최단거리를 dist[i] (i: 1~n) 이라고 했을 때, dist[i]의 최댓값을 모든 정점 v에 대해 구하는 문제이다. 물론 한 정점에서 dist[i]의 최댓값을 구하는건 dfs를 수행하여 쉽게 해결할 수 있지만 모든 정점에 대해 구하게 될 경우 정점의 개수가 5만이므로 시간초과를 보게 될 것이다. 하지만 조금 생각해보면 한 정점에서의 부터 다른 정점으로 부터의 최단 거리 중 최댓값은 트리의 지름의 양 끝 단말 노드 중 하나로의 거리라는 것을 알 수 있다.(만약 트리 지름의 단말 노드가 아닌 다른 리프로 부터의 거리가 최댓값이라면, 트리의 지름보다 긴 거리가 생긴다는 뜻이므로 모순이된다.) .. 더보기
BOJ)14657 준오는 최종인재야!! 문제:icpc.me/14657 문제를 해석해보자면 최대한 많이 문제를 푸는건 결국 주어진 트리를 가중치 없는 그래프에서의 지름에 해당 되는 정점들을 선택하는 경우이다. 하지만 같은 크기를 가지는 지름이 많을 수 있기 때문에 모든 지름을 탐색해야한다. 이를 위하여 지름의 중심이 되는 점을 찾은 뒤 그 점부터 이동 가능한 가장 먼 leaf로의 최단거리를 탐색한 다음 계산해준다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include #include #include #in.. 더보기
BOJ)5038 Flight Planning 문제: icpc.me/5038 트리가 주어질 때 하나의 간선을 삭제하고 다시 하나의 간선은 연결하여 만든 트리의 지름이 최소가 되도록 하는 문제이다. N제한이 2500밖에 안되기 때문에 모든 간선을 다 삭제해 본 뒤 지름을 비교해보는걸 생각해볼 수 있다. 그렇다면 하나의 간선을 제거하였을 때 트리의 지름이 최소가 되도록 간선을 이어붙이려면 어떻게 붙여야할까? 바로 트리의 반지름을 이용하면 된다. 트리의 간선을 하나를 제거하면 두개의 트리가 생기게 된다. 이 때 두 트리의 반지름을 각각 구해준 뒤 반지름을 형성하는 정점들 사이에 간선을 연결하면 트리의 지름은 max(트리1의 지름,트리2의 지름,트리1의 반지름+트리2의 반지름+1)이 된다. 따라서 모든 경우에 대하여 트리의 지름을 구해준 뒤 비교하여 답을 .. 더보기
BOJ)8872 빌라봉 문제: icpc.me/8872 문제의 내용을 풀어서 설명하면 결국 포레스트가 주어졌을 때 해당 포레스트에 몇개의 간선을 추가하여 만들어진 트리의 지름의 최솟값을 구하는 문제이다. 문제의 답은 세 경우중 하나가 될 수 있는데 1.기존의 포레스트내의 트리에서의 지름중 최댓값 2-3. 포레스트 내부의 서브트리들의 반지름 중 가장큰 반지름을 가지는 서브트리에 나머지 반지름들을 길이 L로 연결하였을 때2.가장 긴 반지름 + 두번째로 긴 반지름 +L3.두번째로 긴 반지름 + 세번째로 긴 반지름 +L+L 이 세값 중 최댓값이 답이된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555.. 더보기