목록트리의 지름 C++ (2)

1일1알

백준 1167 트리의 지름 C++

트리의 지름 구하는 법: 1. 임의의 정점x를 정한다. 2. x에서 가장 멀리있는 정점 y를 구한다. 3. y에서 가장 멀리 있는 정점까지의 거리가 트리의 지름이다. 출처 : https://blog.myungwoo.kr/112 트리의 지름 구하기 트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다: 1. 트리에서 임의의 정점 $x$를 blog.myungwoo.kr 위에서 나온 트리의 지름을 구하는 방법만 알고 있으면 dfs를 이용해서 쉽게 구현할 수 있다. #include #include #include #include #include #include #include #include #include..
알고리즘 2022. 6. 20. 12:18
백준 1967번 트리의 지름 C++

루트부터 시작해서 자식들 중 가장 긴 두 경로를 재귀적으로 탐색하는 방식으로 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int ans = 0; struct Node { vector childs; }; map mp; int GetDiameter(int root) { if (mp.find(root) == mp.end()) return 0; vector dists(mp[root].childs.size()); ..
알고리즘 2022. 6. 17. 11:58
이전 Prev 1 Next 다음