[알고리즘] 다익스트라 - 미로 탈출
다익스트라 알고리즘
이 문서에서는 다익스트라 알고리즘의 개념과 작동 방식과 프로그래머스의 [미로 탈출] 문제를 설명해요.
다익스트라 알고리즘은 그래프의 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이에요.
컴퓨터 네트워크, 내비게이션 등 경로 탐색이 필요한 여러 분야에서 사용할 수 있어요.
다익스트라 알고리즘은 다음과 같은 핵심 개념을 기반으로 해요.
가중치 그래프 : 간선마다 음수가 아닌 가중치가 존재하는 그래프
출발점 : 최단 경로를 시작할 노드
거리 배열 : 각 노드 사이의 최단 거리
우선순위 큐 : 방문할 노드 중 가장 누적 비용이 적은 순으로 정렬하는 큐
정점의 개수를 V, 간선의 개수를 E라고 할 때, 다익스트라 알고리즘의 시간 복잡도는 다음과 같이 계산해요.
우선순위 큐를 사용하는 경우 시간복잡도는 O(VlogV + ElogV)에요.
각 반복문마다 미방문 노드 중 출발점으로부터 현재까지 누적 최단 거리를 우선순위 큐로 갱신하는 데 O(VlogV) 시간이 걸려요.
각 노드마다 이웃한 노드의 최단 거리를 갱신하는 데 O(ElovV) 시간이 걸려요.
만약 음의 가중치가 존재하는 경우 벨만-포드 알고리즘을 사용 해야해요.
다익스트라 알고리즘은 보통 다음의 절차를 따라요.
거리 배열 초기화
출발 노드의 거리는 0, 나머지 노드는 무한대로 설정해요.
가장 가까운 노드 선택
큐의 출발점과 인접한 노드들을 선택하여 큐에 추가해요.
거리 갱신
선택된 노드의 인접 노드를 확인하면서, 출발점으로 부터 방문하지 않은 경로가 발견되면 계속 거리 배열 갱신을 해요.
모든 노드가 방문되거나, 더 이상 갱신할 ...
