[프로그래머스] 배달 - Python

문제

배달

아이디어

다익스트라로 풀면 되겠다.. 해놓고 우선순위 큐를 사용하려다 그럴 필요없어 보여서 덱을 사용하고 말았다.

우선 다익스트라라고 생각했던 이유는
간선에 가중치가 주어졌고, 한 정점(노드)에서 모든 정점까지의 최단 경로를 구하는 문제였기 때문이다.

다익스트라(dijkstra) 알고리즘은 다음과 같이 동작한다.

1. 출발 노드를 설정한다(큐에 삽입).
2. 거리비용을 저장할 배열을 무한대의 값으로 초기화한다.
3. 현재 노드와 인접한, 방문하지 않은 노드로 가는 거리를 계산한다.
4. 해당 노드로 가는 비용이 지금까지 구한 값보다 더 작으면 갱신하고 큐에 삽입한다.
5. 3, 4의 과정을 큐가 빌 때까지 반복

구현하면 다음과 같다.

cost = [1e9] * (N+1)

cost[1] = 0
hq = [(cost[1], 1)]
while hq:
    c, cur = heappop(hq)
    if cost[cur] < c: continue
    
    for nxt in range(1, N+1):
        if cost[nxt] > c+adj[cur][nxt]:
            cost[nxt] = c+adj[cur][nxt]
            heappush(hq, (cost[nxt], nxt))

내가 초기에 작성한 야매 코드보다 다익스트라가 더 빠른 실행 속도를 보였다.
내 코드는 ‘지금까지 구한 비용 < 현재 비용’ 인 경우 pass 하지 않기 때문에 조금 더 느렸다고 생각한다.

전체 코드

• 다익스트라 풀이

from heapq import heappop, heappush

def solution(N, road, K):
    answer = 0
    adj = [[1e9]*(N+1) for _ in range(N+1)]
    for a, b, c in road:
        adj[a][b] = min(adj[a][b], c)
        adj[b][a] = min(adj[b][a], c)
    cost = [1e9] * (N+1)
    
    cost[1] = 0
    hq = [(cost[1], 1)]
    while hq:
        c, cur = heappop(hq)
        if cost[cur] < c: continue
        
        for nxt in range(1, N+1):
            if cost[nxt] > c+adj[cur][nxt]:
                cost[nxt] = c+adj[cur][nxt]
                heappush(hq, (cost[nxt], nxt))
        
    for i in range(1, N+1):
        if cost[i] <= K:
            answer += 1
    
    return answer

• 초기 풀이

from collections import deque

def solution(N, road, K):
    answer = 0
    adj = [[1e9]*(N+1) for _ in range(N+1)]
    for a, b, c in road:
        adj[a][b] = min(adj[a][b], c)
        adj[b][a] = min(adj[b][a], c)
    cost = [1e9] * (N+1)
    
    dq = deque([1])
    cost[1] = 0
    while dq:
        cur = dq.popleft()
        for nxt in range(1, N+1):
            if adj[cur][nxt] != 1e9 and cost[nxt] >= cost[cur]+adj[cur][nxt]:
                cost[nxt] = cost[cur]+adj[cur][nxt]
                dq.append(nxt)
        
    for i in range(1, N+1):
        if cost[i] <= K:
            answer += 1
    
    return answer