BootCamp
[Java] DFS(깊이 우선 탐색)이란? Stack을 활용한 예제
안녕하세요 오늘은 DFS에 대해 알아보겠습니다. DFS는 Depth First Search의 약자이며, 깊이 우선 탐색이라고 부릅니다. 루트 노드나 임의의 노드에서 시작하여 최대로 진입할 수 있는 깊이까지 탐색한 후 돌아와 다른 노드로 탐색하는 방식입니다. Stack을 사용하여 데이터를 탐색합니다. 1. DFS (Depth First Search)의 장점과 단점 깊이 우선 탐색은 최대한 깊이 내려간 후 더 이상 깊이 갈 곳이 없으면 옆으로 이동합니다. 예를 들어, 미로 찾기에서는 최대한 한 방향으로 직진합니다. 더 이상 길이 없으면 Stack을 pop 하며 길을 찾아갑니다. ● 장점 현 경로상의 노드들만 기억하면 되므로 저장 공간 수요가 비교적 적습니다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구..
