[알고리즘] 프로그래머스 - 가장 먼 노드

프로그래머스 - 가장 먼 노드

내 풀이

from collections import deque
import sys
import heapq as hq
from collections import defaultdict
from collections import Counter

def dijkstra(start, graph):
    distances = [sys.maxsize] * (len(graph.keys())+1)
    distances[0] = -1
    distances[1] = 0
    q = deque()
    q.append((start, 0))
    while q:
        node, cost = q.popleft()
        for adj_node in graph[node]:
            if distances[adj_node] > cost + 1:
                distances[adj_node] = cost + 1
                q.append((adj_node, cost + 1))

    return Counter(distances)[max(distances)]


def solution(n, edge):
    graph = defaultdict(list)
    for edg in edge:
        graph[edg[0]].append(edg[1])
        graph[edg[1]].append(edg[0])

    return dijkstra(1, graph)

일반 다익스트라를 사용하면 풀리는 문제다.