[ Lv 3 ] 가장 먼 노드

풀이 과정

---

1. 1번에서 시작하여 각각의 노드들에 대한 최단 경로를 구해준다(Dijkstra 알고리즘 사용)

2. 이번 문제에서는 간선의 가중치가 무조건 1이므로 따로 heap를 써줄 필요는 없으므로 deque 사용

3. 최단 경로중 거리가 가장 먼 경로의 개수를 구해주면 된다.

---

from collections import deque

def solution(n, edge):
    answer = 0
    INT_MAX = 99999999999
    queue = deque()
    distance = [INT_MAX] * (n+1)
    graph = [[] for _ in range(n+1)]

    for s, e in edge:
        graph[s].append(e)
        graph[e].append(s)

    distance[1] = 0
    queue.append(1)
    while queue:
        p = queue.popleft()
        for nx in graph[p]:
            if distance[nx] > distance[p] + 1:
                distance[nx] = distance[p] + 1
                queue.append(nx)

    distance[0] = 0
    mdistance = max(distance)
    answer = distance.count(mdistance)

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges