깊이 우선 탐색(DFS, Depth-First Search)은 그래프 탐색 알고리즘 중 하나로, 시작 노드에서부터 시작하여 한 분기마다 가능한 깊이까지 탐색하고, 더 이상 탐색할 수 없을 때 다시 돌아와 다른 분기를 탐색하는 방식입니다. 스택(Stack)이나 재귀 함수를 이용하여 구현됩니다.
DFS의 주요 특징은 다음과 같습니다:
- 깊게 탐색: 현재 노드에서부터 가능한 한 깊이까지 탐색하며, 더 이상 깊게 탐색할 수 없을 때 되돌아옵니다. 이런 특성으로 브랜치나 경로를 완전히 탐색하며, 많은 경우 해를 빠르게 찾을 수 있습니다.
- 스택 또는 재귀 사용: 스택 자료구조를 이용하거나, 재귀 함수 호출을 통해 구현할 수 있습니다. 현재 노드에서 가능한 다음 노드로 이동하면서 스택에 저장하거나 재귀 호출을 하고, 더 이상 이동할 수 없을 때 이전 노드로 돌아와 다음 분기로 탐색합니다.
- 방문 표시: 각 노드를 방문한 노드인지 여부를 표시해야 합니다. 이를 통해 무한 루프를 피하며 모든 노드를 정확히 한 번씩 방문할 수 있습니다.
DFS의 구체적인 작동 방식은 다음과 같습니다:
- 시작 노드를 선택하고, 해당 노드를 방문했다고 표시합니다.
- 현재 노드와 연결된 노드 중에서 아직 방문하지 않은 노드를 선택하고, 해당 노드를 방문했다고 표시합니다.
- 선택한 노드로 이동하여 2단계를 반복합니다.
- 현재 노드와 연결된 모든 노드를 방문했다면, 이전 노드로 돌아갑니다.
- 이전 노드로 돌아갔을 때, 더 이상 방문하지 않은 노드가 없거나 모든 노드를 방문했다면 종료합니다.
DFS의 활용 예시:
- 그래프 탐색: 그래프 내에서 특정 노드를 찾거나 연결된 경로를 찾을 때 사용됩니다.
- 위상 정렬: 방향 그래프에서 노드를 선형 순서로 나열할 때 사용됩니다.
- 그래프의 사이클 판별: 방향 그래프에서 사이클이 존재하는지 여부를 판별할 때 사용됩니다.
- 그래프의 연결성 판별: 무방향 그래프에서 모든 노드가 연결되어 있는지 판별할 때 사용됩니다.
DFS는 재귀 호출을 사용하므로, 너무 깊이 들어가게 되면 스택 오버플로우 등의 문제가 발생할 수 있습니다. 이런 경우에는 반복문을 이용한 BFS(Breadth-First Search)를 고려할 수 있습니다.
아래는 Python으로 구현된 깊이 우선 탐색(DFS)의 예시 코드입니다. 이 코드는 간선과 노드를 딕셔너리를 이용해 표현한 무방향 그래프에서 DFS를 수행하는 예시입니다.