가장 먼 노드

• 그래프에서 BFS를 사용해서 모든 노드까지의 거리를 찾아주면 끝. 그 뒤에는 그중에서 가장 긴 거리가 얼마인지 구하고, 그만큼 떨어져 있는 노드의 갯수를 세면 된다.
• 처음에 엣지 리스트로 주어진 그래프 표현을 인접행렬 형태로 바꾸는 것에 O(E)가 걸리고, BFS에는 O(E+V), 나머지 작업은 O(V). 전체 시간은 O(E+V)

"""Solution code for "Programmers 49189. 가장 먼 노드".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/49189
- Solution link: http://www.teferi.net/ps/problems/programmers/49189
"""

from teflib import search


def solution(n, edge):
    graph = [[] for _ in range(n)]
    for u, v in edge:
        graph[u - 1].append(v - 1)
        graph[v - 1].append(u - 1)

    dists = search.min_distances(graph.__getitem__, 0)
    return dists.count(max(dists))

• Dependency: teflib.search.min_distances