깊이 우선 탐색

깊이 우선 탐색(DFS: deepth-first search)

• 그래프의 시작 노드에서 출발해 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
• 깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등

깊이 우선 탐색의 핵심 이론

• DFS는 한 번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 리스트가 필요
• 그래프는 인접 리스트로 표현
• DFS의 탐색 방식은 후입선출 특성을 가지므로 스택을 사용

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

• DFS를 위해 필요한 초기 작업: 인접 리스트로 그래프 표현하기, 방문 리스트 초기화하기, 시작 노드 스택에 삽입하기

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

• 이제 pop을 수행하여 노드를 꺼낸다. 꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하며 방문 리스트를 체크.

3. 스택 자료구조에 값이 없을 때 까지 반복하기

• 앞선 과정을 스택 자료구조에 값이 없을 때까지 반복.
• 이미 다녀간 노드는 방문 리스트를 바탕으로 재삽입하지 않는 것이 핵심