dfs

한 방향으로 갈 수 있는 만큼 깊게 탐색한 후 막히면 되돌아와 다른 경로를 찾는 방식이다. 스택(Stack)이나 재귀 호출을 사용하여 구현하며, BFS에 비해 메모리 사용량이 적다는 장점이 있다. 하지만 무한 루프에 빠질 위험이 있고 최단 경로를 보장하지 않으므로 탐색 깊이 제한 등의 추가적인 처리가 필요할 수 있다.