배달 - 파이썬

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

프로그래머스

---

내 풀이

 

1.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

def solution(N,road,K):
    graph = [[] for _ in range(N+1)]
    distance = [INF] * (N+1)
    distance[1]=0
    for r in road:
        graph[r[0]].append((r[1],r[2]))
        graph[r[1]].append((r[0],r[2]))
    def ekdlrtmxmfk():
        q=[]
        heapq.heappush(q,(0,1))
        
        while q:
            dist,now = heapq.heappop(q)
            #print((dist,now))
            #print(dist)
            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]))
    ekdlrtmxmfk()
    #print(graph)
    #print(distance)
    return len([x for x in distance if x<=K])

2.

 

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

def solution(N,road,K):
    graph = [[] for _ in range(N+1)]
    distance = [INF] * (N+1)
    distance[1]=0
    for r in road:
        graph[r[0]].append((r[2],r[1]))
        graph[r[1]].append((r[2],r[0]))
    def ekdlrtmxmfk():
        q=[]
        heapq.heappush(q,(0,1))
        
        while q:
            dist,now = heapq.heappop(q)
            #print((dist,now))
            #print(dist)
            if distance[now] < dist:
                continue
            for i,j in graph[now]:
                if i+dist < distance[j]:
                    distance[j] = i+dist
                    heapq.heappush(q,(dist+i,j))
    ekdlrtmxmfk()
    
    return len([x for x in distance if x<=K])

---

대표적인 다익스트라 알고리즘이다.

너무 오랜만에 풀어서 진짜 한참 헤맸다..

처음에는 visit를 만들어서 풀었는데, 시간초과 나서 heapq을 썼다.

다익스트라 알고리즘이 적용가능할 때는 음의 값이 없을때임을 명심해야한다.

1 번풀이 2번풀이 둘다 비슷한데 1번은 이코테의 내용을 참고했다.

1번이 좀 더 직관적인 풀이법같다.

두 풀이법의 가장 큰 차이점은, (노드,가중치 ) 의 순서가 다르다.

 

---

다른사람의 풀이

 

 

---

---