[이코테] 최단 경로_숨바꼭질 (python)

문제

나의 풀이

1. 다익스트라 풀이

import heapq
n, m = map(int, input().split())

graph = [[] for _ in range(n + 1)] # 헛간의 정보를 담을 list
INF = int(1e9)
distance = [INF] * (n + 1) # 최단 거리 정보를 담을 list

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append((b, 1))
    graph[b].append((a, 1))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        d, node = heapq.heappop(q) # 거리, 현재 노드
        if distance[node] < d: # 현재 노드의 거리가 이미 최단 거리라면
            continue
        for i in graph[node]: # 현재 노드와 연결된 다른 노드 확인
            dist = d + i[1] # 거리를 갱신할 준비
            if dist < distance[i[0]]: # 인접 노드의 거리가 최단 거리가 아니라면
                distance[i[0]] = dist # 거리 갱신
                heapq.heappush(q, (dist, i[0]))
                
    for i in range(n + 1):
        if distance[i] == INF:
            distance[i] = -1
            
    m_d = max(distance)
    return distance.index(m_d), m_d, distance.count(m_d)

print(*dijkstra(1))