[Python] 프로그래머스 배달

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

프로그래머스

풀이

양방향 그래프에서 1번노드를 시작으로, 모든 연결 노드까지의 최단 거리를 구한 후 K 이하의 노드 갯수를 세면 되는 문제입니다. 다익스트라 알고리즘을 사용해 문제를 해결할 수 있습니다.

 

1. 양방향 그래프 만들기

2. 다익스트라 알고리즘 

 

다익스트라 알고리즘은 우선순위 큐를 사용해 구현할 수 있습니다.

1. 모든 노드를 최대 거리(INF)로 초기화 합니다.

2. heapq에 (키, 값) 형태로 넣어줍니다.

3. 새로운 값이 기존 시간보다 작은 경우 인접 노드들에 대해 (재)검사를 합니다. 마찬가지로 현재 노드를 지나서 인접 노드로 향하는 것(cost)이 기존의 인접노드로 가는 시간(times[adj[0]])보다 작다면 업데이트 해줍니다.

import heapq

INF = 1e9

def solution(N, road, K):
    answer = 0 
    
    times = [int(INF) for _ in range(N+1)]

    # set graph 
    graph = [[] for _ in range(N+1)]
    for info in road:
        graph[info[0]].append((info[1], info[2])) # (노드, 시간)
        graph[info[1]].append((info[0], info[2]))
    
    # dijkstra
    q = []
    heapq.heappush(q, (0, 1)) # (시간, 노드) 1번 노드 시작
    times[1] = 0
    
    while q:
        time, now = heapq.heappop(q)
        
        if times[now] < time:
            continue
        
        for adj in graph[now]:
            cost = time + adj[1]
            # 거쳐 온 경우가 현재보다 작다면 시간 업데이트 
            if cost < times[adj[0]]:
                times[adj[0]] = cost
                heapq.heappush(q, (cost, adj[0]))
    
    for time in times:
        if time <= K:
            answer+=1
    
    return answer