[백준 / BOJ] 1967 트리의 지름

문제

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

1967번: 트리의 지름

가중치를 가진 트리가 주어진다.

이때, 트리의 지름을 구하는 문제이다.

 

트리의 지름은 트리의 모든 경로들중 가장 긴 경로를 말한다. (가장 긴 경로를 지름으로 하는 원을 그리면, 모든 노드들을 해당 경로안에 집어넣을수있다.)

 

풀이

전형적인 트리의 지름을 구하는 문제다.

BFS,DFS,다익스트라 등으로 풀수있는데, 최단시간으로 답을 구하는 방법은 다익스트라라고 생각해서 다익스트라로 구현했다.

(BFS혹은 DFS의경우 더 작은 가중치가 나올경우 경로를 중복해서 볼수있는데, 다익스트라는 항상 최단경로로 가기때문에, 시간이 더 짧을거라고 생각했음)

 

아이디어는

임의의 노드에서 가장 먼 노드 A를 찾는다. 

위에서 찾은 A노드에서 가장 먼 노드 B를 찾는다.

이때, 노드 B와 노드 A의 거리가 트리의 지름이다.

 

위 아이디어를 그대로 구현했는데, 다익스트라 2번 수행하면된다.

1. 다익스트라를 한번수행해서 임의의 노드에서 가장먼 노드 A를 찾는다.

2. 다익스트라를 한번더 돌려서 노드 A에서 가장 먼 지점 B를 찾는다.

이때, B에 저장된 값이 답이다.

 

소스코드

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

devxb/JJUNalgo