백준 1167. 트리의 지름

티스토리 뷰

tose33 2022. 8. 23. 12:29

1167번: 트리의 지름

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지

www.acmicpc.net

백준 1967. 트리의 지름

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의..

tose33.tistory.com

위 1967번과 이름도 같고 내용도 같은 문제였다.

1967번을 풀었을때는 모든 리프 노드들에 대하여 dfs로 다른 노드까지의 거리를 구해서 풀었는데 풀고난 후 다른 분들 코드를 보니 트리의 지름을 구하는 방법이 있었다.

이번에는 그 방법으로 풀었다.

트리의 지름 구하는 법

1) 임의의 노드 a에서 가장 먼 노드b를 찾는다.

위 그림에서 임의의 노드를 5로 정하면 가장 먼 노드는 거리 11+9+10=30인 노드 12이다.

2) 찾은 노드 b에서 가장 먼 노드 c를 찾는다.

b노드는 12이고 이 노드에서 가장 먼 노드는 거리 10+9+11+15=45인 9이다.

3) b-c가 트리의 지름이다.

공지사항

최근에 올라온 글

최근에 달린 댓글

링크

글 보관함