[알고리즘] 프로그래머스 - 배달

1. 문제

프로그래머스 - 배달

 

2. 접근

1. 모든 노드에서 모든 노드로 가는 간선의 길이가 다 주워져있고, 모든 노드로 접근을 하기에 플로이드로 접근을 해보았다

2. a <-> b 가는 통로가 하나가 아니라 두개가 되기에 나올 수 있는 간선의 길이 중 최단거리를 구한다

3. a == b 인 경우는 간선의 길이가 0임을 보인다

4. 시작이 1부터임을 알 수 있기에, graph[1]을 기준으로 갈 수 있는 노드들의 간선의 길이의 합이 k보다 작은게 있다면 count를 늘려준다

 

 

3. 풀이

# 양방향 , 1 ~ n, 1번에서 시작, k 시간 내, 
def solution(n, road, K):
    INF = int(1e9)
    graph = [[INF]*(n+1) for _ in range(n+1)]
    
    # a == b 이면 같은 노드이기 때문에 거리가 0이다.
    for a in range(1,n+1):
        for b in range(1,n+1):
            if a == b:
                graph[a][b] = 0
              
    # a <-> b 를 연결하는 도로가 여러개가 있을 수 있으므로 최소거리를 구해야한다
    for i in road:
        graph[i[0]][i[1]] = min(graph[i[0]][i[1]], i[2])
        graph[i[1]][i[0]] = min(graph[i[1]][i[0]], i[2])
    
    # a -> b, a -> k -> b 중에서 더 짧은 거리를 구하면 된다.
    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])
                
    count = 0
    # 시작은 1부터 한다
    for a in graph[1]:
        if a <= K:
            count += 1
                
    return count