DFS는 알고리즘 문제를 풀다 보면 꼭 마주하는 개념인 거 같은데요
Code up 문제들을 풀면서 마주한 그래프 문제들을 DFS 문제들로 많이 해결해 왔기에
오늘은 깊이 우선 탐색(DFS)에 대해 알아보고 어떤 상황에 활용하는 게 좋은지 정리해보려 합니다.
DFS란 무엇인가?
DFS(Depth-First Search) 는 그래프 탐색 알고리즘 중 하나로, 특정 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방식입니다. 스택 자료구조를 기반으로 동작하며, 재귀(Recursion) 또는 명시적 스택(Stack)을 사용하여 두 가지 방법으로 구현할 수 있습니다.
DFS를 알아야 하는 이유
1. 그래프 탐색의 기본!!
DFS는 그래프 탐색의 기본적인 방법 중 하나로, 여러 가지 문제에서 응용 됩니다. 미로 탐색, 네트워크 연결확인, 퍼즐 문제 등 다양한 곳에서 사용됩니다
2. 백트래킹(Backtraking)의 핵심
DFS는 백트래킹 기법을 사용할 때 기본적으로 활용됩니다. 백트래킹을 이해하려면 DFS를 숙지하는 것이 필수적입니다.
3. 효율적인 탐색
BFS(너비 우선 탐색)와 함께 DFS는 탐색 문제 해결의 핵심 도구로 활용되며, 문제의 특성에 따라 DFS를 선택하는 것이 효율적인 경우가 많습니다.
DFS의 동작 방식
1. 시작 노드를 방문하고 방문처리
2. 방문한 노드와 연결된 노드 중 방문하지 않은 노드로 이동
3. 더 이상 방문할 노드가 없다면 이전 노드로 되돌아가기
4. 모든 노드를 방문할 때까지 이 과정을 반복
DFS 활용 예시
1. 미로 탐색
DFS를 이용하면 미로에서 출구를 찾거나 특정 경로를 탐색할 수 있다.
2. 백트래킹
N - Queen 문제, 순열 생성, 조합 문제 등 경우의 수를 모두 탐색해야 하는 문제에서 DFS를 활용할 수 있다.
3. 위상 정렬
방향 그래프에서 선행 관계가 있는 작업을 정렬하는 데 사용된다.
4. 연결 요소 찾기
그래프에서 서로 연결된 그룹을 찾을 때 DFS를 활용할 수 있다.
마무리
DFS는 그래프 탐색에서 가장 기본적이고 중요한 알고리즘이다. 다양한 문제 해결에 활용되므로, 재귀와 스택을 활용한 구현 방법을 숙달하는 것이 중요하다. 앞으로 백트래킹, 위상 정렬, 경로 탐색 문제를 풀 때 DFS를 적극적으로 활용해 볼 계획이다.
다음 포스트에서는 DFS를 활용한 문제들 어떻게 풀었는지 소개하도록 하겠습니다.