DFS(Depth-First Search , 깊이 우선 탐색)
- 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘
- 반복물을 활용하거나 재귀문을 통해서 구현된다
장점 :
- 현재 순회중인 정점만 저장하는 스택 데이터 구조를 사용하기 때문에 BFS에 비해 메모리 공간이 절약된다.
- 목표가 특정 정점에 최대한 빨리 도달하는 것일때 유용하다.
단점:
- 순환 그래프의 경우 DFS가 무한 루프에 빠질 수 있다.
- 최단 경로를 찾으려는 경우 최적의 알고리즘이 아닐 수 있다.
DFS 구현방법
- 반복구현 (Stack 구조)
- 재귀함수
DFS 를 설명하기 위해 예시 하나를 보여드리겠다. (백준 24479번)
반복구현 : Stack 의 특징인 후입선출(LIFO) 구조를 사용하여 방문할 정점을 추적한다.
1. 알고리즘은 임의의 정점에서 시작하여 방문한 것으로 표시하고 스택에 푸시한다.
2. 스택에서 맨 위 정점을 가져온다.
3. 방문하지 않은 모든 인접 정점을 방문하여 방문한 것으로 표시하고 스택으로 푸시한다.
4. 스택이 비워질 때까지 프로세스를 반복한다.
글로만 설명하면 이해가 쉽지 않아 그림으로 자세히 설명해보겠다.
Stack에는 방문할 노드들을 push 해서 담는다 .
처음 1노드를 방문했으면 Stack 에 1 를 담는다.
1노드를 방문했으면 자식 노드인 2 와 4를 탐색할 수 있다.
방문을 완료한 1은 Stack 에서 제거를 해준다.
1의 자식노드인 2 와 4를 Stack에 담아 탐색을 준비한다.
DFS 는 깊이 탐색으로 1의 자식노드인 2 와 4를 동시에 탐색 할 수 없다.
2노드를 탐색하기로 했으면 2에 대한 모든 자식 노드를 탐색 완료 후 다시 4노드를 탐색 하는 것이다.
Stack 의 특성 후입선출로 2노드를 먼저 탐색하게 된다.
방문을 완료난 2는 Stack 에서 제거를 해준다.
2의 자식노드인 3 과 4 중에 4는 이미 방문을 한 것 임으로 3 노드를 Stack에 담아 탐색을 시작한다.
3의 방문하지 않은 자식노드가 없으므로 더이상 탐색하지 않는다.
Stack에 담긴 모든 노드를 꺼내 탐색을 종료한다.
*(Stack) 반복 구현 방식
public static void dfs(int v)
{
//1.스택에 생성
Stack<Integer> stack = new Stack<>();
//2. 스택에 v 노드 담기
stack.push(v);
//3. v노드 방문함
visited[v] = true;
while(!stack.isEmpty())
{
//4. stack 비어있지않으면 가장 최근 노드 꺼내기
int node = stack.pop();
//5. 최근 노드에 연결된 노드 있는지 확인
for(int n : adj[node])
{
//6. 해당 노드에 방문하지 않았으면
if(!visited[n])
{
//6. 연결된 노드 stack에 넣기 , 방문함
stack.push(n);
visited[n]=true;
}
}
}
*재귀 함수 방식
그래프에 모든 노드에 방문하는 것으로 모든 노드를 방문해야하는 문제에서 유용하다.
public static void dfs(int v)
{
//1. 노드 방문
visited[v] = true;
//2. 해당 노드이 인접한 노드들 탐색
for(int nb : adj[v])
{
//3. 방문하지 않은 노드
if(!visited[nb])
//4. 재귀 호출로 다시 탐색
dfs_j(nb);
}
}
코드로 보면 재귀함수 방식이 더 쉬울 것 같지만 그래프가 커져 순환이 많이해야하는 경우 오버플로가 발생할 수 있기에 반복구현이 더 적합 할 수 있다.
처음 DFS에 대해서 공부할때 유튜브 동영상도 보고 다른사람이 풀어논 수식도 보고 했지만 이해가 쉽지 않았다.
노트 한장 꺼내서 직접 노드 하나하나 그려 구조를 파악하고 순환이 어떻게 되는지 스택에는 어떻게 들어가는건지 직접 이해하는게 최고의 방법이라고 생각한다.
그 이후에 문제를 접하면 20% 이해가 되고 비슷한 문제를 반복하면서 풀다보면 어떠한 문제에 DFS 를 사용해야할지 BFS를 사용해야할지 감이 잡힌다.
한마디로 손으로 그리고 반복학습이 최고!