1. 문제 설명

배달

2. 문제 분석

그래프 내 존재하는 모든 정점에 대한 특정 정점 간의 최단 거리를 통해 답을 도출해야 한다. 즉 다익스트라 알고리즘을 통해 풀 수 있다. 다익스트라 알고리즘은 양방향, 단방향 모두 사용 가능하며 자기 자신을 제외한 나머지 정점과의 거리를 INF로 설정한 뒤 알고리즘을 실행한다. 이후 그 정점(인덱스로 표현)에 대한 최단 거리를 담은 배열이 반환된다.

1. 출발 노드 → 도착 노드 및 비용을 리스트로 기록한다.
2. 각 노드에 대한 거리를 담을 리스트를 설정, 초기 상태에 위치한 노드(여기에서는 1번)를 제외한 나머지 노드와의 거리는 INF가 디폴트.
3. 초기 상태에서 출발, 인접 노드 정보를 담은 리스트를 활용해 'TO' 노드와 인접한 모든 노드가 바로 그 비용을 사용할 수 있다. 최단 거리를 갱신한다.
4. 그래프의 모든 노드에 대한 특정 노드와의 거리가 반환된다.

3. 나의 풀이

import heapq

def dij(distance, edges):
    heap = []
    heapq.heappush(heap, [1, 0])
    # [정점, 비용]을 힙에 넣는다. 시작 지점 1번, 비용 0.

    while heap:
        vertex, cost = heapq.heappop(heap)
        # 힙에서 정보를 꺼내 '어디로 갈 때' '얼마'가 드는지 체크.
        for v, c in edges[vertex]:
            # 그 '어디'를 사용한 모든 루트 내에서 지금까지 계산해놓은 최단 거리와 지금 들어온 거리를 비교한다.
            if cost + c < distance[v]:
                distance[v] = cost + c
                heapq.heappush(heap, [v, cost+c])
                # 모든 간선을 확인하면서 1번에서 각 정점으로 향하는 최단 거리가 distance에 기록된다.

                
def solution(N, road, K):

    edges = [[] for x in range(N+1)]
    for route in road:
        cur, post, cost = route
        edges[cur].append([post, cost])
        edges[post].append([cur, cost])
    # 출발지를 제외한 모든 마을에 대한 디폴트 값은 INF. K<=500000이므로 500001로 설정.
    
    distance = [500001]*(N+1)
    distance[1] = 0
    dij(distance, edges)
    # 다익스트라 알고리즘을 통해 그래프 내 모든 정점과 특정한 정점 간의 최단 거리를 모두 구한다.
    
    return len([x for x in distance if x <= K])

• 그래프 알고리즘을 매우 중요하므로 사용 방법을 정확하게 익히자.