DFS에서 재귀를 사용하는 방법 vs 스택을 사용하는 방법 DFS(Depth-First Search)에서 **재귀를 사용하는 방법**과 **스택을 사용하는 방법**은 사실상 같은 논리를 구현하지만, 사용하는 스택의 종류가 다를 뿐이에요: 1. **재귀를 사용하는 DFS**: 재귀 호출은 시스템 스택을 이용해 함수 호출 정보를 저장해요. 이 경우, 재귀 함수가 호출될 때마다 시스템 스택에 함수 호출이 쌓이고, 함수가 종료되면 스택에서 빠져나가는 방식으로 동작해요. 즉, **시스템의 호출 스택(Call Stack)**을 직접 이용하는 거죠. 2. **스택을 사용하는 DFS**: 이 방법은 명시적으로 `stack` 자료구조를 사용하여 구현해요. 우리가 직접 스택을 선언하고, 노드를 추가(push)하고 제거(pop)하면서 DFS를 수행하는 거예요. 재귀 없이 반복문(while)을 사용하여 스택이 빌 때까지 탐색을 진행하죠. 정리하자면, **재귀 DFS는 시스템 스택을 사용하는 DFS**이고, **명시적 스택을 사용하는 DFS는 우리가 직접 관리하는 스택을 사용하는 DFS**라는 차이가 있을 뿐, 알고리즘의 동작 방식은 동일합니다. 두 방법의 차이점으로는 다음이 있어요: - **시스템 스택(재귀)**은 깊이가 깊어질수록 스택 오버플로우(Stack Overflow) 위험이 커질 수 있어요. 보통 C/C++ 같은 언어에서는 재귀 깊이가 수천~수만 이상이 되면 스택 오버플로우를 발생시킬 수 있죠. - **명시적 스택**을 사용하면 스택 크기를 코드에서 제어할 수 있기 때문에, 매우 깊은 트리 구조에서도 상대적으로 안전하게 사용할 수 있어요. 따라서, **스택의 크기와 깊이가 중요한 문제**에서는 재귀보다 명시적 스택을 사용하는 것이 더 안전할 수 있습니다. ## 재귀는 항상 지양해야 하나? 그렇다고 재귀를 무조건 피할 필요는 없어요. 상황에 따라 재귀와 명시적 스택(반복문) 중 어떤 것을...