깊이 우선 탐색(DFS, Depth-first search)
1. DFS란?
- 트리나 그래프를 순회하는 방법중의 하나이다. DFS와 대응되는 다른 탐색 방식으로는 BFS가 있다.
- 그래프 순회에서 분기(branch)가 발생할 경우 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 말한다. 다음 그림과 같은 탐색 순서를 따른다.
2. DFS의 구현
DFS의 구현 방법에는 두가지 방법이 있다.
- 재귀 호출: 더 깊은 노드로 진행할 때 재귀호출을 사용한다. (함수 콜 스택 사용)
- 스택 사용: 스택을 직접 사용해 방문한 노드를 저장했다가 꺼낸다.
재귀 호출을 사용한 구현 (C)
그래프를 탐색하는 함수만 구현하였다.
#include <stdio.h>
int visit[99]; // 방문 여부 기록용
int node[99][99]; // 그래프를 인접 행렬로 기록했다고 가정, 0번은 NULL.
void dfs(int cur){ // cur: 현재 노드의 번호
visit[cur] = 1; // 방문 여부 기록
for(int i=0;i<99;i++){ // cur 노드의 다음번 노드 탐색
if(node[cur][i] != 0 && visit[i]) // 다음번 노드가 존재하고 방문하지 않았을 경우
dfs(node[cur][i]); // 다음번 노드를 인자로 재귀 호출
}
return;
}
스택을 사용한 구현 (C++ STL <stack> 사용)
스택 또는 C++의 <stack>이 궁금하다면 여기
#include <cstdio>
#include <stack>
using namespace std; // STL 선언
int main(void){
int visit[99];
int node[99][99];
stack<int> s; // 스택 선언
s.push(1); // 1번 노드로부터 출발한다고 가정
visit[1] = 1;
while(!s.empty()){
int cur = s.top(); // 스택에서 현재 노드 추출
s.pop();
for(int i=0;i<99;i++){
if(node[cur][i] != 0 && visit[i]){
s.push(node[cur][i]); // 다음번 노드를 스택에 push
visit[i] = 1;
}
}
}
return 0;
}