- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
- 표준 라이브러리 형태로 지원
<힙(Heap)>
- 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나
- 최소 힙(Min Heap), 최대 힙(Max Heap) 존재
- Min Heap = 값이 낮은 값부터 추출
- Max Heap = 값이 높은 값부터 추출
- 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용
- 리스트는 삽입에 굉장히 빠른 시간이 소요되지만 삭제에는 전체 데이터를 돌아야한다.
- 힙의 이진트리 형태를 이용한다.
사용예제
1. 최소 힙
import heapq
#오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
h = []
result = []
#모든 원소를 차례대로 힙에 삽입
for value in iterable:
heapq.heappush(h, value)
#힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for i in range(len(h)):
result.append(heapq.heappop(h))
return result
result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)#출력 결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
2. 최대 힙
import heapq
#내림차순 힙 정렬(Heap Sort)
def heapsort(iterable):
h = []
result = []
#모든 원소를 차례대로 힙에 삽입
for value in iterable:
heapq.heappush(h, -value)
#힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for i in range(len(h)):
result.append(-heapq.heappop(h))
return result
result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)- 최대 힙은 지원하지 않기 때문에 그냥 거꾸로 (-)를 붙여서 살짝 하면 된다.
#출력 결과
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
<새로 알게된 것>
#힙에 데이터 삽입
heapq.heappush(리스트, 값)
#힙에서 데이터 추출
heapq.haeppop(리스트)1. 개선된 구현 방법
- 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙(Heap) 자료구조를 이용
- 다익스트라 알고리즘이 동작하는 기본 원리는 동일
- 현재 가장 가까운 노드를 저장해 놓기 위해서 힙 자료구조를 추가적으로 이용
- 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용
2. 다익스트라 알고리즘: 동작 과정 살펴보기(우선순위 큐)
[Step 0]
- 그래프를 준비하고 출발 노드를 설정하여 우선순위 큐에 삽입한다.
- 노드 1에대한 거리를 0으로 설정해서 큐에 넣는다.
- 나머지는 모두 무한으로 초기화시키고
- 매 단계마다 각각의 경우를 고려한다.
[Step 1]
- 우선순위 큐에서 원소를 꺼낸다. 1번 노드는 아직 방문하지 않았으므로 이를 처리한다.
- 1이랑 인접한 노드 2, 3, 4를 확인한다.
- 2번,3번,4번 노드는 각각 현재 값이 무한(초기화)에서 1번을 거쳐갈때 (2, 5, 1)을 더한 값을 비교
- 현재 값 > 거쳐갈 때 이므로 갱신 여부는 True로 바뀐다.
- 갱신될때만 큐에 이와같은 정보를 넣어준다.
- 리스트에 각각 노드번호 2,3,4는 거리가 2,5,1로 갱신되었으며
- 우선순위 큐에는 거리가 짧은 순서대로 노드번호 4,2,3이 기록됐다.
[Step 2]
- 우선순위 큐에서 원소를 꺼낸다.
- 4번 노드는 아직 방문하지 않았으므로 이를 처리한다.
- 노드 4까지 최단 거리가 1이라는 담긴 원소를 꺼낸다.
- 노드 4를 거쳐가는 3, 5를 확인한다.
- 3번노드는 현재 값 5 > 거쳐갈 때 1+3 이므로 4로 갱신된다.
- 5번노드는 현재 값 > 거쳐갈 때 1+1이므로 2로 갱신된다.
- 리스트도 갱신이 되었고 우선순위 큐에도 이 두 정보를 넣어준다.
- 다시한번 큐내에서 거리가 낮은 순서대로 밀린다.
[Step 3]
- 우선순위 큐에서 원소를 꺼낸다. 2번 노드는 아직 방문하지 않았으므로 이를 처리한다.
- 2번노드와 근접한 4와 3번 노드를 확인한다.
- 3번 노드의 경우 현재 값 4 < 거쳐갈 값 2+3 이므로 갱신하지 않는다.
- 4번 노드의 경우도 갱신하지 않는다.
- 우선순위큐도, 리스트도 갱신되지 않는다.
[Step 4]
- 우선순위 큐에서 원소를 꺼낸다. 5번 노드는 아직 방문하지 않았으므로 이를 처리한다.
- Step3에서 직전에 있넌 거리:2, 노드:5를 꺼낸다.
- 노드 5번과 인접한 3번, 6번노드를 비교해보고 현재 값, 거쳐간 값을 비교한다.
- 둘다 현재 값 > 거쳐갈 값이므로 갱신해주고
- 우선순위 큐에도 넣어준다. 마찬가지로 전거와 새로 들어온 가리 순으로 다시 정렬된다.
[Step 5]
- 우선순위 큐에서 원소를 꺼낸다. 3번 노드는 아직 방문하지 않았으므로 이를 처리한다.
- 노드 3번 기준으로 2번노드와 6번노드를 확인한다.
- 하지만 두 노드다 현재 값 < 거쳐갈 때 값 이므로 수정되지 않는다.
[Step 6]
- 우선순위 큐에서 원소를 꺼낸다. 3번 노드는 이미 방문했으므로 무시한다.
- 방문했는지 안했는지 기록하는 테이블이 있으면 좋지만 너무 비효율적이고 전 거리를 대비해서 그 값을 유사하게 구할 수 있으므로 하지 않는다.
- 꺼낸 원소의 거리는 4지만 이미 3번 노드 번호의 거리는 3이므로 할 필요가 없다.
[Step 7]
- 우선순위 큐에서 원소를 꺼낸다. 6번 노드는 아직 방문하지 않았으므로 이를 처리한다.
- 노드 6번과 인접할 수 있는 간선이 존재하지 않으므로 테이블 또한 갱신되지 않고 우선순위 큐도 변동되지 않는다.
3. 개선된 구현 방법
INF = int(1e9)
#노드의 개수, 간선의 개수 입력받기
n, m = map(int, input().split())
#시작 노드 번호를 입력받기
start = int(input())
#각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for i in range(n + 1)]
#최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)
#모든 간선 정보를 입력받기
for _ in range(m):
a,b,c = map(int, input().split())
#a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].append((b,c))
def dijkstra(start):
q = []
#시작 노드로 가기 위한 최단 거리는 0으로 설정하여, 큐에 삽입
heapq.heappush(q, (0,start))
distance[start] = 0
while q: #큐가 비어있지 않다면
#가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
#현재 노드가 이미 처리된 적이 있는 노드라면 무시
if distance[now] < dist:
continue
#현재 노드와 연결된 다른 인접한 노드들을 확인
for i in graph[now]:
cost = dist + i[1]
#현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
#다익스트라 알고리즘 수행
dijkstra(start)
#모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
#도달할 수 없는 경우, 무한이라고 출력
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])4. 개선된 구현 방법 성능 분석
'CodingTest > 최단 경로 알고리즘' 카테고리의 다른 글
| 미래 도시 (0) | 2022.07.16 |
|---|---|
| 전보 (0) | 2022.07.16 |
| 플로이드 워셜 알고리즘 (0) | 2022.07.16 |
| 최단 경로 문제 (다익스트라) (0) | 2022.07.16 |