문제풀이/프로그래머스
배달(프로그래머스) 문제풀이
soo-dal
2024. 4. 5. 09:55
문제
https://school.programmers.co.kr/learn/courses/30/lessons/12978
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 접근 방식
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
회고
저번에 할 때는 공부를 하고 문제를 풀어서 코드를 작성하는데 어려움이 없었는데, 따로 공부를 안하고 다익스트라를 구현하려다 보니 조금씩 실수하는 부분이 생기고 시간이 조금씩 지체되었다. 계속 까먹을 것 같아서 핵심 동작 과정만 기억해두려한다