프로그래머스_python_배달

문제

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

코딩테스트 연습 - 배달

풀이

간단한 다익스트라

dfs & bfs 방식으로 각 노드를 탐색한다.

중복을 체크하는 방식

• dfs & bfs 방식과 이 부분만 다르다
• 지금의 방식이 이전보다 비용이 적게 들때만 탐색을 계속한다.

개선된 다익스트라

간단한 다익스트라에 탐색할 노드를 선정하는 방식이 개선되었다.

최소 heap을 사용하여 가장 적은 비용이 드는 노드부터 검증한다.

플로이드 워셜

다익스트라와 마찬가지로 최단경로 알고리즘이다.

2차원 테이블에 점화식을 사용해서 최소비용을 채워넣는다. (dp)

N 개의 노드에 N^2번의 연산을 수행하므로 노드의 개수가 큰 경우에는 불리하다

"""
1~4 노드가 있고
1번 노드를 거쳐하는 경우
"""
for i in range(노드개수) : 
    for j in range(노드개수) : 
        D[i][j] = min(D[i][j], D[i][1]k+D[1][j])

"""
D23 = min(D23, D21+D13)
D24 = min(D24, D21+D14)
D32 = min(D32, D31+D12)
D34 = min(D32, D31+D14)
D42 = min(D42, D31+D12)
D43 = min(D43, D41+D13)
"""

비슷한 문제

프로그래머스_경주로 건설

 

코드

import heapq

def solution(N, road, K):
    # connect node
    graph = {i : list() for i in range(N+1)}
    for n, m, w in road : 
        graph[n].append((w, m))
        graph[m].append((w, n))
    
    # search
    weight = [K+1, ]*(N+1) # 모든 마을에 가기 위해 K+1만큼의 비용이 필요하다고 가정
    heap = [(0, 1)] 
    while heap : 
        # update weight
        w, n = heapq.heappop(heap)
        weight[n] = min(weight[n], w)
        
        # add child node
        cnodeList = graph[n]
        for cw, cnode in cnodeList :
            if cw+w < weight[cnode] :
                newnode = (cw+w, cnode)
                heapq.heappush(heap,newnode)
    
    return sum([w<=K for w in weight])