7/2 탐색 알고리즘 - BFS, DFS, 다익스트라

용어	뜻	예시/활용
노드	그래프에서 하나의 위치나 상태	맵 칸, 도시, 퀘스트 상태
간선	노드와 노드를 연결하는 관계	길, 이동 가능 방향
BFS	가까운 곳부터 넓게 탐색하는 방식	최단 칸 수, 전파 범위
DFS	한 방향으로 깊게 들어갔다 돌아오는 방식	백트래킹, 경로 존재
다익스트라	가중치가 있는 그래프의 최단 비용 탐색	지형 비용이 다른 길찾기

DFS / BFS

다익스트라

다익스트라 알고리즘은 ++음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드++에서 각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다.

다익스트라 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만,

더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것으로도 사용한다.

다익스트라 알고리즘은 그리디 알고리즘이자 다이나믹 프로그래밍 기법을 사용한 알고리즘이라고 볼 수 있다.

비교

구분	그리디 알고리즘	다익스트라 알고리즘
의미	알고리즘을 설계하는 방식	최단 경로를 구하는 구체적인 알고리즘
핵심	현재 가장 좋은 선택을 반복	현재 거리가 가장 짧은 정점을 선택
목적	문제에 따라 다름	시작점에서 각 정점까지의 최단 거리 계산
최적해 보장	문제의 조건에 따라 다름	음수 가중치가 없으면 보장
관계	상위 개념	그리디 방식을 사용하는 알고리즘