DFS, BFS에 대해 알아보자 얻어갈 지식 DFS, BFS DFS( Depth-First Search : 깊이 우선 탐색) 깊이 우선 탐색은 그래프에서 한 루트로 더 이상 내려갈 곳이 없을 때까지 검색한 뒤 옆으로 이동하여 다른 루트를 검색하는 방식이다. 보통 한없이 깊이 검색하는 것을 방지하기 위해 깊이 제한을 사용한다. 깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 가장 최근 노드의 부모 노드로 되돌아와서, 이전과는 다른 노드를 선택한다. 여기서 부모 노드로 되돌아오는 과정을 백트리킹이라 한다. 장점 단지 현 경로상의 노드만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라..
