목록트리의 중심 (1)
블로그 옮겼습니다
BOJ 14657번 준오는 최종 인재야!!
http://boj.kr/14657 문제에서 주어진 세개의 조건을 통해 N개의 문제들은 트리를 이루고 있다는 것을 알 수가 있다. 그럼 가장 많은 문제를 풀기 위해서는 트리에서의 가장 긴 단순 경로를 찾으면 되며, 트리에서의 가장 긴 단순 경로는 바로 트리의 지름이 되기 때문에 트리의 모든 지름 중에 경로상에 포함된 에지들의 가중치합이 최소가 되는 지름을 찾는 문제로 볼 수가 있게된다. 트리의 모든 지름을 체크하기 위해 우선 트리의 중심을 찾고 그 중심을 기준으로 답을 구해보자. 하지만 트리의 중심은 1개 혹은 2개이기 때문에 두개의 케이스를 나누어보자. 1. 트리의 중심이 1개인 경우 트리의 중심이 1개인 경우에는 단순하다 트리의 중심으로 부터 거리가 지름/2 인 노드들까지의 경로들 중 그 경로상에 존..
Algorithm/Problem Solving
2017. 7. 23. 15:55