테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 가장 먼 노드 ======

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

===== 코드 =====
<dkpr py>
"""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))
</dkpr>
  * Dependency: [[:ps:teflib:search#min_distances|teflib.search.min_distances]]

{{tag>프로그래머스 ps:problems:programmers:Level_3}}