-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
템플릿 코드에서 if cur_v not in costs: 부분에 의문이 있습니다.
24.01.20 15:57 작성 조회수 112
1
def dijkstra(graph, start, final):
# 각 노드들의 비용을 저장
costs = {}
# 우선순위 큐
pq = []
# (해당위치까지 가는 총 비용, 노드위치)
heapq.heappush(pq, (0, start))
while pq:
# heappop을 하면 가장 작은 원소가 튀어 나온다.
cur_cost, cur_v = heapq.heappop(pq)
# 방문하지 않은 백터 일때만 작동
if cur_v not in costs:
#
costs[cur_v] = cur_cost
for cost, next_v in graph[cur_v]:
next_cost = cur_cost + cost
heapq.heappush(pq, (next_cost, next_v))
return costs[final]해당 템플릿 코드중에서
if cur_v not in costs:
costs[cur_v] = cur_cost어떻게 costs에 cur_v가 없다는 것 만으로 바로 최적의 경로라고 확신할 수 있는지 의문이 있습니다.
heapq의 성질덕에 cur_cost, cur_v가 '지금까지 heap에 넣은 값들중에' 가장 작은 값 인거는 알겠는데 다른 경로를 통해 뒤늦게 heap에 들어간 값이 이전에 costs에 not in이여서 넣은 값보다 작은 경우도 있지 않나요??
뭔가 제 생각에 자연스럽지 않아서 다른 코드들을 찾아보니 아래와 같이 제가 생각한 조건대로 대소 비교를 해보고 넣더군요.
def dijkstra(graph,start,end):
costs = {vertex:111111 for vertex in graph}
pq = []
heapq.heappush(pq,(0,start))
while pq:
cur_cost, cur_v = heapq.heappop(pq)
if costs[cur_v] < cur_cost:
continue
for cost, next_v in graph[cur_v]:
next_cost = cur_cost + cost
if next_cost < costs[next_v]:
costs[next_v] = next_cost
heapq.heappush(pq, (next_cost, next_v))
return costs[end]
" '지금까지 heap에 넣은 값들중에' 가장 작은 값 " 이 아니라 앞으로 나올 값 중에 가장 작은 근거가 있을까요??
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
답변을 작성해보세요.
1
개발남노씨
지식공유자2024.01.21
안녕하세요. 민수님.
질문의 내용 모두 파악했습니다.
코드 스타일에 따라 민수님께서 찾아본 다른 코드처럼 대소비교를 하는 코드로 민수님만의 템플릿 코드를 만드는게 좋을 것 같아요. 구현하는 데에는 다양한 방법이 있기때문에 그중에서 나에게 자연스럽게 이해가 되는 코드를 사용하는게 좋거든요~
그럼에도 불구하고 궁금하신거죠,
" '지금까지 heap에 넣은 값들중에' 가장 작은 값 " 이 아니라 앞으로 나올 값 중에 가장 작은 근거가 있을까요??'"
이게 가능한 이유를 간단히 설명해드릴게요.
A에서 시작해서 F까지 가는 경로중에 10의 cost가 드는 경로를 발견해서 heap에 넣었어요. 하지만, 앞으로 나올 경로중에 10보다 작은 값이 나올 수 있어요. 민수님 말씀대로.
예를 들면 A->B->F 는 9라고 해볼게요. 그러면 결국 A->B로 가는 경로는 9보다 작겠죠. 그래서 아까 계산됐던 10의 cost가 heap에서 pop되어서 쓰이기 전에 A->B로 가는 경로가 heap에 들어갈거고, 결국 A->B->F로 가는 경로도 10의 cost가 pop되기 전에 heap에 저장될 거에요.
그러면 결국 A->F 10의 cost가 쓰이기 전에 A->B->F 9의 cost가 발생하는 경로가 먼저 사용되겠죠. 근데 A->C->F가 5의 cost가 든다면, 결국 9의 cost가 heap에서 pop 되기 전에 또, heap에 저장이 될거에요.
이런식으로 하다보면 결국 A에서 F로 가는 모든 경로중에서, 가장 먼저 도착한게 제일 cost가 적은게 돼요.
혹시 이해가 잘 안된다면, 강의에서 제가 보여드렸던 코드 + 그래프 그림 을 하나씩 살펴보시면 민수님께서 햇갈려하시는 내용이 해결이 될거에요.
하지만 아까 말씀드렸듯이 자기 자신에게 쉽게 이해되는 코드가 가장 좋은코드에요! 그러니 민수님께서 작성하신 코드를 잘 활용하는 것이 더 좋아보입니다 :)
또 궁금하신점 있으면 언제든 편하게 질문주세요~
0
김민수
질문자2024.01.22
질문하고 나서 질문이 애매해서 제대로 된 대답을 못들을 꺼라고 예상했는데 제가 생각한 요지를 정말 잘 생각해서 대답해주셨네요. 감사합니다. 덕분에 애매하던 생각들이 완벽하게 이해됐습니다.
제가 이해하는데 도움이 되었던 생각을 적어보자면
핵심은 BFS처럼 너비를우선적으로 탐색하면서 Heap의 우선순위가 합쳐져서 costs에 넣은 값보다 나중에 탐색된 값이 더 우선순위가 높을수 없다 라고 생각했습니다.
DFS처럼 코드가 적혀있다면 A->B까지 탐색하고 F까지 탐색하는 시간이(코드상에서 시간)
A->C->F 보다 먼저 일어날수 있어요.
그럼 A->B->F가 A->C->F보다 작은지 큰지 모르는 상태로 먼저 탐색되고 값이 costs에 들어가 버릴꺼에요.
하지만 개발남노씨의 코드는 BFS의 구조 + Heap자료구조 형태이기 때문에 일단 첫번째 노드에서 연결된 모든 노드를 탐색한(1->2(5), 1->4(1)가 있다고 가정) 다음에 그 중 우선순위 높은 쪽으로 pop이 되고 그 다음에 또 우선순위가 높은 쪽으로 이동합니다. 즉 만약에 1->4->? 로 가는 총합이 1->2로 가는 우선순위보다 높다면 1->2는 또 heap에서 뒤로 밀려납니다. 이렇게 작동하니까..
costs에 넣는 값은 항상 우선순위가 가장 높은 값이 확정되었을때 heap에서 pop되는 거라고 이해 했습니다.
원래 처음에는 다른사람도 이해시키겠다고 글 적은건데 그건 좀 힘드네요. 쨋든 저는 이해했습니다.
감사합니다.
답변 2