사용자 도구

사이트 도구


ps:problems:programmers:49189

가장 먼 노드

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호49189
문제명가장 먼 노드
레벨Level 3
분류

BFS

시간복잡도O(E+V)
인풋사이즈V<=20,000, E<=50,000
사용한 언어Python
해결날짜2021/06/30
태그

고득점 Kit - 그래프

풀이

  • 그래프에서 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))

토론

댓글을 입력하세요:
T W G V​ D
 
ps/problems/programmers/49189.txt · 마지막으로 수정됨: 2021/07/02 14:46 저자 teferi