팔만코딩경
/
Library DB
/
[알고리즘] 트리의 지름 증명 및 적용
Search
Duplicate
Share
🌳
[알고리즘] 트리의 지름 증명 및 적용
간단소개
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
Algorithm
C++
Scrap
태그
9 more properties
[알고리즘 / 백준] 트리의 지름 알아보기 (BOJ 1967/ BOJ 1167)
"트리에 존재하는 모든 경로 중 가장 긴 것의 거리" 를 구하는 문제를 마주쳤을 때, 어떤 방식으로 이를 해결해야 할까? 브루트포스적인 접근 방식으로 bfs(넓이 우선 탐색)을 통해 모든 정점에서의 최대 거리를 구해야 할까? 고민을 하던 중 주변의 도움을 받아 알게 된 해결 방법을 공부해보고자 한다.
"트리에 존재하는 모든 경로 중 가장 긴 것의 거리"
를 구하는 문제를 마주쳤을 때, 어떤 방식으로 이를 해결해야 할까? 브루트포스적인 접근 방식으로 모든 정점에서 bfs(넓이 우선 탐색)을 통해 최대 거리를 구해야 할까? 고민을 하던 중 주변의 도움을 받아 알게 된 해결 방법을 공부해보고자 한다.
트리와 트리의 지름에 대해서 알아본 뒤, 트리의 지름을 구하는 방법을 증명해보고 백준에서 관련 문제를 해결해보았습니다 :-)