[ Lv 2 ] 배달

- Floyd 알고리즘을 적용하여 모든 정점에서 다른 정점에 도달하는 최소 거리를 구해준다.(최대 50개의 마을까지이므로, 더 늘어나면 dijkstra 알고리즘 적용)

- 이후 distance[1]을 조사하여 1번 마을에서 K 거리 이내의 마을들의 개수를 출력해주면 된다.

import copy
def solution(N, road, K):
    INT_MAX = 9999999999
    matrix = [[INT_MAX] * (N+1) for _ in range(N+1)]
    for a, b, c in road:
        if matrix[a][b] > c:
            matrix[a][b] = c
            matrix[b][a] = c

    distance = copy.deepcopy(matrix) 

    for i in range(1, N+1):
        distance[i][i] = 0

    # floyd Algorithm
    for i in range(1, N+1):
        for j in range(1, N+1):
            for k in range(1, N+1):
                distance[j][k] = min(distance[j][k], distance[j][i] + distance[i][k])


    # 1에서 도달 가능한 개수 출력
    answer = len(list(filter(lambda x:x<=K, distance[1])))

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges