배달(프로그래머스) 문제풀이

문제 

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

프로그래머스

 

 

 

문제 접근 방식

1~N개의 마을이 존재하고 1번 마을에서 다른 마을로 K 시간 이하로 배달 가능한 마을의 수를 구하는 문제이다. k 시간 이하로 배달 가능한지 여부를 알기 위해서 1번 마을에서 각 마을로 가는 최단 거리를 구할 필요가 있었고, [단일노드 > 모든 노드] 로의 최단 거리를 구하는 양의 가중치 그래프 문제이기 때문에 다익스트라 알고리즘을 사용하였다.

 

1. 다익스트라를 활용해서 [1번 > 모든 마을]로의 최단거리를 구한다
2. k 시간 이하로 배달 가능한 마을의 수를 센다

 

 

시간 복잡도

다익스트라를 활용시 시간복잡도는 O(Elog(E)) ≒ O(Elog(V)) 며, V와 E의 최댓값이 각각 50, 2000이므로 시간내에 동작한다.

 

 

코드

import heapq
INF=int(1e9)


def solution(N, road, K):
    adj=[[] for _ in range(N+1)]
    d=[INF]*(N+1)
    
    ## 인접리스트 초기화
    for s,e,dist in road:
        adj[s].append((e,dist))
        adj[e].append((s,dist))
    
    ## 우선순위큐를 활용한 다익스트라 알고리즘
    pq=[]
    heapq.heappush(pq,(0,1))
    while pq:
        dist,node=heapq.heappop(pq)
        if d[node]<dist:
            continue
        d[node]=dist
        for next,n_dist in adj[node]:
            if dist+n_dist<d[next]:
                d[next]=dist+n_dist
                heapq.heappush(pq,(dist+n_dist,next))
    answer=0
    for dist in d:
        if dist<=K:
            answer+=1

    return answer

 

 

회고

저번에 할 때는 공부를 하고 문제를 풀어서 코드를 작성하는데 어려움이 없었는데, 따로 공부를 안하고 다익스트라를 구현하려다 보니 조금씩 실수하는 부분이 생기고 시간이 조금씩 지체되었다. 계속 까먹을 것 같아서 핵심 동작 과정만 기억해두려한다