프로그래머스 - Lv.3 배달 문제를 푸는 과정에서 학습한 내용

  • 다익스트라 알고리즘 개념
  • BFS VS 다익스트라(Dijkstra) 차이점
  • Python에서 우선순위 큐(Priority Queue) 사용법
  • 최소 힙(min heap) VS 우선순위 큐(Priority Queue) 차이점(이걸 학습했다고 해야하나 애매하긴 하지만..)


문제는 간략하게 말하면, 시작 노드에서 모든 노드에 최단 시간(거리)의 경로로 탐색했을 때 조건으로 주어진 시간 내에 도착할 수 있는 노드의 개수를 구하는 것이다.

BFS를 떠올렸지만, BFS에 대한 이해가 부족해서인지 응용은 쉽지 않았다.(방문한 노드에 대한 방문 처리를 하는데, 다른 노드로 부터 진행한 경로도 비교를 해야 했기에..)

그래서 하루 내내 고민하다가 결국 힌트를 보고, 다익스트라 알고리즘을 찾아봤다.

다익스트라 알고리즘 설명을 봤는데.. 그렇구나.. 하면서 읽다가 문득 “뭐지? BFS랑 똑같은 것 같은데..?” 생각이 들었고, 왜 난 못 풀었는데 다익스트라 알고리즘 풀이 방식은 된다고 하는걸까 해서 찾아본 결과,

BFS와 다익스트라 알고리즘의 차이는 ‘가중치의 유무’ 였다. (+ 다익스트라에서는 노드에 대한 방문처리를 하지 않는다. 한번 지난 간선을 다시 이용하지 않는 것!) BFS의 경우는 최대한 적은 노드를(그러니까 모든 간선 길이가 똑같다고 가정했을 때 최소 거리) 거쳐서 인접 노드를 우선으로 최단 거리를 찾는 방법이고,

다익스트라 알고리즘의 경우 간선 길이가 다른 조건에서 최단 거리를 구해주는 것이었다..!

다익스트라 알고리즘은 파이썬에서 보통 우선순위 큐로 구현을 한다고 한다. 여기서 다시 “우선순위 큐(Priority Queue)는 무엇인가..?” 문제에 봉착해서 찾아보니까, 또 “최소 힙(min heap)이랑 뭐가 다른거지..?” 해서 찾아봤다..

이 내용은 아직 잘 모르지만, 최소 힙은 스레드의 안전을 보장하지 않고 우선순위 큐는 스레드의 안전을 보장해준다고 한다.

스레드에 대한건 차차 공부해나가야 할 것 같다..


우선순위 큐(Priority Queue) - Python

from queue import PriorityQueue

# 최소 힙(min heap)과 사용 방법 거의 똑같다
queue = PriorityQueue() # 우선순위 큐 생성
queue.put(3) # 우선순위 큐에 삽입 (= heapq.heappush())
queue.get() # 최소값 반환 후 삭제 (= heapq.heappop())