'트리의 지름' 태그의 글 목록

[Baekjoon] 1167_트리의 지름

Gold II문제(출처: https://www.acmicpc.net/problem/1167) 문제 풀이 처음에는 정점 1에서 dfs 탐색을 통해 지름을 구했다. 내가 구현한 코드 방식으로는 만약 정점 1에서 3개의 자식이 있다면 각 DFS를 통해 3개의 거리를 더한 값이 트리의 지름이 되는 것이었다. 하지만 트리의 지름은 임의의 두 점 사이의 거리 중에서 가장 긴 것을 뜻하므로 제대로 된 답을 구할 수 없었다. 트리의 지름을 구하는 방법을 찾아보니 다음과 같았다.1. DFS를 통해 임의의 정점(a)으로부터 가장 먼 정점(b)을 구함2. 가장 먼 정점(b)으로부터 DFS를 통해 가장 먼 정점(c)을 구함3. 2번에서 구한 가장 먼 정점(b)과 새로 구한 가장 먼 정점(c)의 거리가 트리의 지름이 된다. ..

🌞Algorithm/🔥Baekjoon 2024.02.02

일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28

Melody Coding

트리의 지름 1

티스토리툴바