[Level2] 배달

🛠 문제

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

👩🏻‍💻 해결 방법

최단 경로를 구해야했기 때문에 다익스트라로 해결하는 것은 쉽게 알 수 있었다
출발점과 도착점이 정렬? 되어있지 않았기 때문에 처음에는 새로운 그래프에 정렬된 road를 저장하여 풀었는데 테스트 케이스를 모두 통과하지 못했다...
따라서 heap에서 꺼낸 시작점(now)과 같은 출발점들을 for문 안에서 모두 찾아주고 방문하며 거리 비용을 최소값으로 갱신해나갈 수 있었다

소스 코드

import heapq
INF = int(1e9)
def solution(N, road, K):
    answer = 0
    dist = [INF] * (N+1)
    q = []
    heapq.heappush(q, (1, 0))  # start, dist
    dist[1] = 0
    
    while q:
        now, cost = heapq.heappop(q)
        for r in road:
            next_cost = cost + r[2]
            if r[0] == now and next_cost < dist[r[1]]:
                dist[r[1]] = next_cost
                heapq.heappush(q, (r[1], next_cost))
            if r[1] == now and next_cost < dist[r[0]]:
                dist[r[0]] = next_cost
                heapq.heappush(q, (r[0], next_cost))
    
    return len([i for i in dist if i <= K])

💡 다른 사람의 풀이

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)