반응형
문제
https://www.acmicpc.net/problem/1167
1167번: 트리의 지름
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지
www.acmicpc.net
풀이
DFS를 사용해서 풀 수 있습니다.
임의의 노드에서 출발하여 가장 먼 거리에 있는 노드를 탐색해줍시다.
임의의 노드에서 출발하여 가장 먼 거리에 있는 노드는 트리의 지름에 포함되는 노드입니다.
가장 먼 거리에 있는 노드를 찾았다면 그 노드에서 부터 가장 깊은 곳이 트리의 지름이 됩니다.
소스코드
후기
처음에는 모든 노드에 대해 DFS나 다익스트라를 해봐야하나... 생각이 들었습니다.
하지만 정점의 개수가 최대 10만이므로, 두 방식으로는 시간초과가 나게됩니다.
블로그 글을 참고해서 풀이하였고, 이런 방법은 직접 떠올리지 못해서 아쉬웠습니다.😂
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 1991 트리 순회 (Swift) (0) | 2023.05.15 |
|---|---|
| [BOJ] 백준 1967 트리의 지름 (Swift) (0) | 2023.05.15 |
| [BOJ] 백준 11725 트리의 부모 찾기 (Swift) (0) | 2023.05.15 |
| [BOJ] 백준 11780 플로이드 2 (Swift) (0) | 2023.05.15 |
| [BOJ] 백준 11779 최소비용 구하기 2 (Swift) (1) | 2023.05.15 |
