프로그래머스. 배달 파이썬 풀이

프로그래머스. Level 2. 배달 파이썬 풀이

문제링크 https://programmers.co.kr/learn/courses/30/lessons/12978

플로이드 워셜 알고리즘을 이용하면 쉽게 해결할 수 있는 문제

def solution(N, road, K):
    answer = 0
    
    INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
    
    # 2차원 리스트(그래프 표현)을 만들고, 모든 값을 무한으로 초기화
    graph = [[INF] * (N+1) for _ in range(N+1)]
    
    # 자기 자신에서 자기 자신으로 가는 거리는 0으로 초기화
    for a in range(1, N+1):
        for b in range(1, N+1):
            if a == b:
                graph[a][b] = 0
    
    # 두 마을 a,b를 연결하는 도로는 여러개가 있을 수도 있다고 했으니 min으로 최솟값을 저장
    for a, b, c in road:
        graph[a][b] = min(graph[a][b], c)
        graph[b][a] = min(graph[b][a], c)
        
    # 플로이드 워셜 알고리즘 수행
    for k in range(1, N+1):
        for a in range(1, N+1):
            for b in range(1, N+1):
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
    
    # 걸리는 시간이 K 이하라면 결과값 +1
    for a in range(1, N+1):
        if graph[1][a] <= K and graph[1][a] != INF:
            answer += 1
    
    return answer