프로그래머스 12978 Python [배달, 다익스트라 알고리즘]

def solution(N, road, K):
    INF = float('inf')
    
    # 인접 리스트 형태로 무방향 그래프 구성
    graph = [[] for _ in range(N + 1)]
    for u, v, w in road:
        graph[u].append((v, w))
        graph[v].append((u, w))
        
    distances = [INF] * (N + 1)
    visited = [False] * (N + 1)
    distances[1] = 0  # 항상 1번 마을을 기준으로 함
    
    # N개의 노드를 순회하며 최단 거리 갱신
    for _ in range(N):
        # 아직 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
        min_dist = INF
        current_node = -1
        
        for node in range(1, N + 1):  # 1번 노드 ~ N번 노드
            if not visited[node] and distances[node] < min_dist:
                min_dist = distances[node]
                current_node = node
                
        # 더 이상 방문할 수 있는 노드가 없으면 탐색 종료
        if current_node == -1: break
            
        visited[current_node] = True  # 첫 시작은 1번 노드 방문부터
        
        # 선택된 노드를 거쳐가는 경로가 기존 경로보다 짧으면 거리 갱신
        for next_node, weight in graph[current_node]:  # 현재 노드에 연결된 노드 중
            cost = distances[current_node] + weight  # 경유 거리
            if cost < distances[next_node]:  # 경유하는 것이 한번에 가는 것보다 빠른 경우
                distances[next_node] = cost  # 최소 거리 갱신
                
    # K 시간 이하로 도달 가능한 마을 개수 계산
    answer = 0
    for d in distances[1:]:  # 1번 마을을 제외한 마을 중
        if d <= K:  # 허용 시간을 충족하는 마을은
            answer += 1  # 카운트
    return answer