7/2 탐색 알고리즘 - BFS, DFS, 다익스트라
| 용어 | 뜻 | 예시/활용 |
|---|---|---|
| 노드 | 그래프에서 하나의 위치나 상태 | 맵 칸, 도시, 퀘스트 상태 |
| 간선 | 노드와 노드를 연결하는 관계 | 길, 이동 가능 방향 |
| BFS | 가까운 곳부터 넓게 탐색하는 방식 | 최단 칸 수, 전파 범위 |
| DFS | 한 방향으로 깊게 들어갔다 돌아오는 방식 | 백트래킹, 경로 존재 |
| 다익스트라 | 가중치가 있는 그래프의 최단 비용 탐색 | 지형 비용이 다른 길찾기 |
DFS / BFS
다익스트라
다익스트라 알고리즘은 ++음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드++에서 각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다.
다익스트라 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만,
더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것으로도 사용한다.
다익스트라 알고리즘은 그리디 알고리즘이자 다이나믹 프로그래밍 기법을 사용한 알고리즘이라고 볼 수 있다.
비교
| 구분 | 그리디 알고리즘 | 다익스트라 알고리즘 |
|---|---|---|
| 의미 | 알고리즘을 설계하는 방식 | 최단 경로를 구하는 구체적인 알고리즘 |
| 핵심 | 현재 가장 좋은 선택을 반복 | 현재 거리가 가장 짧은 정점을 선택 |
| 목적 | 문제에 따라 다름 | 시작점에서 각 정점까지의 최단 거리 계산 |
| 최적해 보장 | 문제의 조건에 따라 다름 | 음수 가중치가 없으면 보장 |
| 관계 | 상위 개념 | 그리디 방식을 사용하는 알고리즘 |
