[알고리즘] 깊이우선탐색(DFS)

1. 개념
2. 쓰는 방법(코드 설명)
3. 어디에 쓰면 좋은가?
4. 예제

깊이우선탐색이란?

개념

• 연결된 노드를 따라서 계속 방문을 한 후에 더이상 연결된 노드가 없을 때 그 전 노드로 되돌아가서 다시 연결된 노드를 따라 탐색을 한다.

DFS 탐색과정

DFS 사용방법

재귀적 구현

• 시작 정점을 선택하고 방문한다.
• 시작 정점의 인접한 정점들 중 방문하지 않은 정점을 하나 선택하여 방문하고, 이 정점을 시작 정점으로 DFS를 재귀적으로 호출한다.
• 더 이상 방문할 인접 정점이 없을 때까지 반복한다.

스택을 이용한 구현

• 스택을 사용하여 현재 경로에 있는 정점들을 기록한다.
• 시작 정점을 스택에 push하고 방문한다.
• 더 이상 방문할 인접 정점이 없으면 스택에서 정점을 pop한다.
• 스택이 빌 때까지 반복한다.

언제 사용하면 좋은가?

• DFS는 미로 탐색, 퍼즐 게임, 네트워크 분석, 경로 탐색 등 다양한 분야에서 사용된다. 그래프가 연결되어 있는지, 또는 그래프 내에 사이클이 존재하는지 등을 판별할 때도 사용된다.
• DFS 구현시 무한 루프에 빠지지 않도록, 이미 방문한 정점은 다시 방문하지 않도록 처리해야 한다. 이를 위해 방문 여부를 기록하는 배열이나 자료구조를 사용한다.

예제