[프로그래머스/python] 배달

[프로그래머스/python] 배달

배달

Summer/Winter Coding(~2018)

​

문제

프로그래머스

​

풀이

다익스트라로 풀었습니다.

​

풀이코드

def min_index(li,visit):
    min_val = 9999999
    min_idx = 0
    for i in range(len(li)):
        if li[i]==0 or visit[i]==True:
            continue
        if li[i]<=min_val:
            min_idx = i
            min_val = li[i]
    return min_idx

def solution(N, road, K):
    answer = 0
    node_map = [[500001 for j in range(N+1)] for i in range(N+1)]
    road.sort()

    v = [False for i in range(N+1)]
    for i in road:
        start, end, dist = i
        node_map[start][end] = min(dist,node_map[start][end])
        node_map[end][start] = min(dist,node_map[end][start])

    dist = node_map[1]
    dist[1] = 0
    v[1] = True
    v[0] = True
    for i in range(N-1):
        current = min_index(dist,v)
        v[current] = True
        for j in range(1, N+1):
            if not v[j]:
                if dist[current] + node_map[current][j] <= dist[j] :
                    dist[j] = dist[current] + node_map[current][j]
    answer = 0 
    for i in dist:
        if K>=i:
            answer+=1
    return answer

​

가장 인기 많은 코드

def solution(N, road, K):
    visited = [False] * (N + 1)
    costs = [float('inf')] * (N + 1)
    costs[1] = 0
    parents = [1]          
    while (parents):
        parent = parents.pop(0)
        visited[parent] = True
        for a, b, cost in road:
            if (a == parent or b == parent):
                target = b if a == parent else a
                if costs[target] > costs[parent] + cost:
                    costs[target] = costs[parent] + cost
                    parents.append(target)

    return sum(1 for c in costs if c <= K)

​