[프로그래머스] 배달

• 링크:
  https://school.programmers.co.kr/learn/courses/30/lessons/12978
• 회고:
  • 하나의 노드에서 다른 모든 노드까지의 최단 거리를 구하면 되고, 각 간선의 비용값은 양수이므로 다익스트라 알고리즘으로 풀면 쉽다.
  • 문제 설명에 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다. 라고 되어 있는데, 이 부분을 a -> b 갈 수 있는 경로는 여러개 존재할 수 있다라는 의미로 해석해서 애먹었음. 실제로 a, b를 바로 연결하는 간선이 2개 이상 있을 수 있다는 뜻이었다. 문제를 주관적으로 해석한 영향...

python

INF = 1e9


def get_smallest_node(visited, distance):
    min_value = INF
    index = 0

    for node in range(1, len(distance)):
        if not visited[node] and distance[node] < min_value:
            min_value = distance[node]
            index = node

    return index


def solution(N, road, K):
    # 노드별로, 해당 노드를 방문한 적 있는지 체크하는 목적의 리스트
    visited = [False] * (N + 1)

    # 최단 거리 리스트 (1번 노드로부터 최단 거리)
    distance = [INF] * (N + 1)

    # 임의 두 노드를 연결하는 도로는 2개 이상 존재 가능. 그 중 최단 거리 구하기
    temp_graph = [[INF for _ in range(N + 1)] for _ in range(N + 1)]
    for a, b, c in road:
        # a <-> b 이동 비용 : c
        if c < temp_graph[a][b]:
            temp_graph[a][b] = c
            temp_graph[b][a] = c

    # 각 노드별 연결되어 있는 노드에 대한 정보
    graph = [[] for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if temp_graph[i][j] != INF:
                graph[i].append((j, temp_graph[i][j]))

    # 1번 노드 방문 & 거리 세팅
    visited[1] = True
    distance[1] = 0
    for connect_node, cost in graph[1]:
        distance[connect_node] = cost

    # 1번 노드 제외한 나머지 노드에 대해서 최단 거리 갱신
    for _ in range(N - 1):
        # 방문하지 않은 노드 중 가장 거리가 짧은 노드
        node = get_smallest_node(visited, distance)

        # 노드 방문 및 거리 세팅
        visited[node] = True
        for connect_node, cost in graph[node]:
            # 현재 노드를 방문해서 지나는 경우가 더 짧은 경우 갱신
            if distance[node] + cost < distance[connect_node]:
                distance[connect_node] = distance[node] + cost

    # k 시간 이하로 배달이 가능한 노드 개수
    count = 0
    for i in distance[1:]:
        if i <= K:
            count += 1

    return count