[Python] 프로그래머스 가장 먼 노드

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

from collections import deque, defaultdict
def solution(n, vertex):
    graph = defaultdict(list)
    distance = {i:0 for i in range(1, n + 1)}
    queue = deque([[1, 0]])

    for a, b in vertex:
        graph[a].append(b)
        graph[b].append(a)

    while queue:
        node, dist = queue.popleft()
        if distance[node] == 0:
            distance[node] = dist

            for i in graph[node]:
                queue.append([i, dist+1])

    distance[1] = 0
    distance = list(distance.values())
    max_dist = max(distance)

    return distance.count(max_dist)

• BFS를 이용해서 1번 노드와 다른 노드들 간의 최소 거리를 구한 후 가장 먼 노드의 갯수를 세었다.
• 처음엔 최소힙을 이용한 다익스트라 알고리즘을 이용해서 풀이하려고 했는데 오히려 시간초과가 났다. 일반 BFS보다 다익스트라 알고리즘이 더 효율적이라고 생각해왔었는데 오히려 더 효율적이지 못했던 것이다. 찾아보니 노드 간의 거리가 모두 똑같은 경우 BFS가 더 효율적일 수 있다고 한다.