길찾기 알고리즘(DFS, BFS, Dijkstra)
길찾기 알고리즘에는 DFS, BFS, 다익스트라, Best-First Search, A* 등 다양한 것이 존재합니다. 그 중 오늘은 DFS와 BFS, 다익스트라에 대해 학습해보겠습니다. 1. DFS (Depth First Search) DFS는 깊이 우선 탐색이라고 하며, 이름에 걸맞게 어떠한 그래프를 탐색할 때 최대한 깊숙히 탐색을 한 후, 더 탐색할 수 없으면 다른 경로를 탐색하는 알고리즘입니다. 만약 위와 같은 그래프가 있고, 2차원 배열로는 저렇게 표현했다고 합시다. 시작점이 노드 A라고 했을 때, DFS 알고리즘으로 그래프를 순회한다면 어떤 순서로 순회를 할까요? - DFS의 순회 과정 - 1) A와 연결된 노드는 B와 C 입니다. A는 자신과 연결된 2개의 노드 중 어떤 노드를 선택할 지 고릅..
