DFS

DFS는 공부했던 자료구조인데도 문제를 푸는데 어려움을 느꼈다.. 오랜만에 해서 그런건지 기억이 가물가물하다… 문제를 봤을 때 DFS와 BFS 어떻게 푸는지 잘 몰랐는데, 기술 매니저님이 문제를 많이 풀어보면 자연스럽게 보인다고하셨다. 두루뭉실하게는 DFS는 찌르는 느낌으로 마지막 까지 깊게 들어가는 반면, BFS는 퍼지는 느낌으로 진행하면 된다고 하셨다.

깊이 우선 탐색(Depth-First Search)

깊이 우선 탐색은 그래프나 트리에서 모든 자식을 탐색한 후 형제 노드로 넘어가는 방식으로 동작하는 탐색 알고리즘 중 하나이다. 이 알고리즘은 스택(Stack) 자료구조나 재귀(Recursion)를 통해 구현할 수 있다. 주로 그래프의 모든 노드를 방문하거나 특정 조건을 만족하는 노드를 찾을 때, 경로 탐색, 연결 요소 확인, 그래프 순회 등에 사용된다.

DFS 풀이 방법

1. 시작 노드를 방문하고, 방문한 노드를 스택에 저장한다.
2. 그 노드의 자식 노드 중에서 방문하지 않은 노드가 있으면 그 노드로 이동한다.
3. 모든 자식 노드를 방문하면 스택에서 노드를 꺼내고, 해당 노드의 형제 노드를 탐색한다.
4. 스택이 비어있을 때까지 위 과정을 반복한다.

DFS는 재귀적으로 구현할 때 자연스럽게 스택을 사용하므로, 스택을 명시적으로 사용하지 않고도 구현할 수 있다.