가장 먼 노드

가장 먼 노드
그래프
2186명 완료

https://programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

그래프를 안다면 어려운 문제는 아니니까.. 모른다면 최단 경로 찾기를 참고... 

https://comdoc.tistory.com/entry/25-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EC%B0%BE%EA%B8%B0

25. 그래프 - 최단 경로 찾기

from collections import deque


def solution(n, edges):
    graph = {}
    for v, w in edges:
        graph.setdefault(v, set()).add(w)
        graph.setdefault(w, set()).add(v)
    queue = deque([1])
    visited = {1}
    path = {1: 0}
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            if w not in visited:
                path[w] = path[v] + 1
                queue.append(w)
                visited.add(w)
    return tuple(path.values()).count(max(path.values()))

테스트 1 〉	통과 (0.08ms, 10.6MB)
테스트 2 〉	통과 (0.06ms, 10.8MB)
테스트 3 〉	통과 (0.08ms, 10.8MB)
테스트 4 〉	통과 (0.41ms, 10.8MB)
테스트 5 〉	통과 (1.51ms, 12MB)
테스트 6 〉	통과 (3.44ms, 19.2MB)
테스트 7 〉	통과 (34.09ms, 88.8MB)
테스트 8 〉	통과 (67.89ms, 125MB)
테스트 9 〉	통과 (63.15ms, 125MB)