Programmers / 2단계 / 배달 / python / Summer/Winter Coding(~2018)

 

코딩테스트 연습 - 배달 | 프로그래머스 스쿨 (programmers.co.kr)

 

 

모범 답안

import heapq

def dijkstra(dist,adj):
    queue = []
    heapq.heappush(queue, [0,1])  
    while queue:
        cost, node = heapq.heappop(queue)
        for c,n in adj[node]:
            if cost+c < dist[n]:
                dist[n] = cost+c
                heapq.heappush(queue, [cost+c,n])


def solution(N, road, K):
    dist = [float('inf')]*(N+1) 
    dist[1] = 0  
    adj = [[] for _ in range(N+1)]  
    for r in road:
        adj[r[0]].append([r[2],r[1]]) 
        adj[r[1]].append([r[2],r[0]])
    dijkstra(dist,adj)
    return len([i for i in dist if i <=K])

import heapq

def dikjstra(start,distance,graph):
    q = []
    heapq.heappush(q, (0,start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now]<dist:
            continue
        for i in graph[now]:
            cost = dist+i[1]
            if cost<distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost,i[0]))

def solution(N, road, K):
    answer = 0
    INF = int(1e9)
    distance = [INF] * (N+1)
    
    graph = [[] for _ in range(N+1)]
    for a,b,c in road:
        graph[a].append((b,c))
        graph[b].append((a,c))
        
    dikjstra(1,distance,graph)
    
    for i in range(1,N+1):
        if distance[i]<=K:
            answer += 1

    return answer

 

참조

[프로그래머스] 배달 / python 파이썬 (tistory.com)

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