문제
https://programmers.co.kr/learn/courses/30/lessons/12978
Prolem About
핵심 키워드
각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려
고 합니다.
위 문장으로 이뤄 봤을 때 가중치가 각각 다른 그래프 중 최단경로를 구해야 하므로 다익스트라 알고리즘을 써야한다.
아래의 그림으로 최단경로를 구하는 문제에서 어떤 알고리즘을 써야 하는지 알 수 있다.
문제 코드
python에서 다익스트라는 구현하기 쉽다. heapq 모듈을 써서 최소비용 지금 갈 수 있는 곳 중에 최소 비용인 거리를 먼저 탐색하면서 안가도 될곳을 안가게 만들게 하면된다.
import heapq
def solution(N, road, K):
# index를 통해서 간선의 위치를 파악해주기 위해서 list 만들기
lst = [[] for _ in range(N + 1)]
# 출바 index애 [cost, 도착index]를 넣어서 list 간선 만들어 주기
for s, e, c in road:
lst[s].append([c, e])
lst[e].append([c, s])
# cost는 최대한 큰 값으로 사용
inf = int(1e9)
cost = [inf] * (N + 1)
# 1번에서 출발하므로 cost[1]은 0을 넣고 Q에 (비용, 현재위치) 넣기
cost[1] = 0
Q = [(0, 1)]
# heapq를 할용한 다익스트라 구현
while Q:
c, n = heapq.heappop(Q)
if cost[n] == c:
for go_cost, go in lst[n]:
now_cost = go_cost + cost[n]
if cost[go] > now_cost and now_cost <= K:
cost[go] = go_cost + cost[n]
heapq.heappush(Q, (now_cost, go))
answer = sum([1 if cost[i] <= K else 0 for i in range(1, N+1)])
return answer
'알고리즘 > 알고리즘 공부(python)' 카테고리의 다른 글
백준_2458_키순서/Using_Python_파이썬 (0) | 2022.06.21 |
---|---|
백준_1916_최소비용구하기/Using Python 파이썬 (0) | 2022.06.21 |
BAEKJOON 19238 스타트 택시 Using Python (0) | 2022.06.16 |
백준(BAEKJOON) 1654 랜선 자르기 using Python (0) | 2022.06.16 |
프로그래머스 (보석 쇼핑) using python (0) | 2022.06.15 |