[Python] 배달

https://programmers.co.kr/learn/courses/30/lessons/12978

---

플로이드 워셜 풀이

 

 

# N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받음
def solution(N, road, K):
    arr = [[float('inf')]*N for _ in range(N)] # 칸을 최대정수로 채운 N*N 격자 생성
    
    for i in range(N):
        arr[i][i] = 0 # 자기 자신으로 오는 칸은 0으로 초기화
    # 격자에 각 마을의 거리 입력
    for r in road:
        i,j,dist = r
        # 격자 인덱스에 맞추기 위해 -1
        i,j,dist = i-1, j-1, dist
        arr[i][j] = min(arr[i][j],dist)
        arr[j][i] = min(arr[j][i],dist) # 거리는 양방향으로 입력
    
    # 모든 격자를 돌며 i에서 k를 경유해서 j를 가는 경우와 i에서 바로 j를 가는 경우의 값을 비교해 가장 짧은 거리를 저장
    for k in range(N):
        for i in range(N):
            for j in range(N):
                arr[i][j] = min(arr[i][k] + arr[k][j], arr[i][j])
 
    # 1번 마을(arr[0])에서 출발하는 경우 중 K 이상인 칸만 개수를 세서 리턴
    return len([i for i in arr[0] if i <= K])