트리 (1) 썸네일형 리스트형 [BOJ 1167] 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net Tag : tree dp 문제요약 트리에서 가장 먼 정점쌍을 찾고 거리를 출력해라. 풀이 두가지 풀이가 존재한다. 1. 탐색 두번 음수 가중치를 가진 간선이 없을 때 성립하는 풀이로 아무 정점에서나 한번 돌려서 가장 먼 점을 찾고 찾은 가장 먼점에서 또 가장 먼 점을 찾는 풀이이다. 위 그림을 보면 아무 정점에서나 먼점을 찾아도 그게 바로 지름의 한쪽 끝이 된다는걸 알 수 있다. .. 이전 1 다음
