컴공생의 다이어리

너비 우선 탐색(BFS, Breadth First Search) BFS는 가까운 노드부터 우선적으로 탐색하는 방식이며 레벨(level) 순서대로 접근한다. BFS는 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용된다. 큐를 활용해서 구현한다. 장점 노드 수가 적고 깊이가 얕은 해가 존재 할 때 유리 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있음 단순 검색 속도가 DFS보다 빠름 단점 재귀호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색 할 노드들을 저장하기 때문에 노드의 수가 많을 수록 필요없는 노드들까지 저장해야 하기 때문에 더 큰 저장공..

깊이 우선 탐색(DFS, Depth First Search) DFS는 그래프에서 깊은 부분(자식들)을 우선적으로 탐색하는 방식이다. DFS는 스택이나 재귀 함수를 사용해서 구현할 수 있다. 탐색 과정이 한없이 진행되는 것을 막고 싶다면 깊이 제한(depth bound)를 사용해서 한업이 진행되는 탐색을 막을 수 있다. 장점 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적음 최선의 경우, 가장 빠른 알고리즘. 운 좋게 항상 해에 도달하는 올바른 경로를 선택한다면, 깊이 우선 탐색이 최소 실행시간에 해를 찾음 찾으려는 노드가 깊은 단계에 있다면 BFS보다 빠르게 찾을 수 있음 단점 찾은 해가 최단 경로가 된다는 보장이 없음 최악의 경우, 가능한 모든 경로를 탐험하고서야 해를 찾으므로, 해..