[백준 / BOJ] 19581 두 번째 트리의 지름

문제

출처 : www.acmicpc.net/problem/19581

19581번: 두 번째 트리의 지름

 

트리가 주어졌을때 두번째로 긴 트리의 지름을 구하는 문제다.

 

풀이

트리의 지름을 구하는 임의의 지점에서 가장 먼지점 A를 찾고, A에서 가장 먼 지점 B를 찾으면 된다.

이걸 좀더 응용하면 되는데, 

 

1. 임의의 지점 O 에서 가장 먼지점 A를 찾고, A에서 두번째로 먼 지점 B를 찾는다.

2. 임의의 지점 O 에서 두번째로 먼지점 C를 찾고, C에서 가장 먼 지점 D를 찾는다.

 

두 값중 max값을 구하면답. 

 

주의할 사항이 있는데, (이것때문에 좀 해맸음) 예제 2번같은 경우다.

 

트리의 구조가

 

2 - 1 - 3 

(1->3 가중치는 3)

(1->2 가중치는 2)

 

위와 같이 연결되어있고, 임의의 지점 O를 1번노드로 잡고 탐색했을때 반례가 존재한다.

위와 같은 상황에서 가장 먼지점 A는 3번 노드이다. 

또한 두번째로 먼 지점 C 는 2번 노드이다.

 

이때 빨간색 글자와같이 C에서 가장 먼지점 D를 찾을경우 가장 먼지점은 5이며, 반례가 생긴다. (출력은 3이되어야함)

이를, 만약 A-B의 거리와 C-D거리가 같다면, 

C에서 두번째로 먼 지점 E와 A에서 두번째로 먼 지점 B를 찾아 비교해주는식으로 예외처리를 해서 풀었다.

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/19581%20%EB%91%90%20%EB%B2%88%EC%A7%B8%20%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EC%A7%80%EB%A6%84/main.cpp

devxb/JJUNalgo