깊이 우선 탐색(Depth First Search, DFS)는 가장 기본적인 그래프 완전 탐색 알고리즘입니다. 그래프의 시작 노드에서 탐색할 한 쪽 분기를 정하여 최대한 깊이 탐색을 마친 후 다음 분기로 넘어가 다시 탐색을 시작합니다.

DFS는 재귀를 이용하여 쉽게 구현할 수 있습니다.
재귀의 특성때문에 깊이가 너무 깊으면 스택 오버플로우가 발생합니다. 따라서 탐색 공간의 깊이가 제한되어 있을때만 사용해야합니다.

스택 사용하여 구현하기

1. 초기화 작업

• 그래프가 있다면 인접 리스트로 그래프 표현하기
• 방문 검사 배열 초기화 하기
• 시작 노드를 스택에 넣어 주기

2. 탐색 진행

• stack.isEmpty()가 true가 될때까지 탐색진행하기 (while문)
• stack.pop()을 통해 노드 꺼내기
• 방문 검사 배열을 통해 중복 검사하기
• 종료조건 검사하기
• 다음 상태 생성하기(범위 검사, 유효성 검사)
• 생성된 다음 상태를 stack.push()하기

스택을 사용하지 않고도 재귀메서드를 호출하여 구현할 수도 있습니다. 편한 방법으로 사용하면 됩니다.