1.DFS(Depth-first search) : 깊이 우선 탐색 ?
-
그래프 완전 탐색 기법 중 하나
-
깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 입니다.
-
깊이 우선 탐색은 실제 구현 시 재귀함수를 이용하므로 스택 오버 플로에 유의해야합니다.
-
깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있습니다.
-
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다.
-
미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사합니다.
-
즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것입니다.
-
사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택합니다.
-
깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단합니다.
-
단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느립니다.
| 기능 | 특징 | 시간 복잡도 |
|---|---|---|
| 그래프 완전 탐색 | 재귀 함수로 구현 , 스택 자료 구조 이용 | O(노드수 + 에지수) |
1-1 그래프 탐색이란?
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지
1-2 깊이 우선 탐색의 핵심 이론
DFS는 한 번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인접 리스트로 표현하겠습니다.
그리고 DFS의 탐색 방식은 후입선출 특성을 가지므로 스택을 사용하여 설명하겠습니다.
2. DFS 의 특징
1 .자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있습니다.
2.전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류입니다.
3 .이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것입니다.
이를 검사하지 않을 경우 무한루프에 빠질 위험이 있습니다.
3.DFS의 탐색 과정
- a 노드(시작 노드)를 방문한다.
방문한 노드는 방문했다고 표시한다.
2.a와 인접한 노드들을 차례로 순회한다.
a와 인접한 노드가 없다면 종료한다.
3.a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
4.b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.
b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.
즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
아직 방문이 안 된 정점이 없으면 종료한다.
있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다.
.
.
사진의 과정을 코드로 간단하게 구현해 보면서 알아보겠습니다 !
DFS의 구현방법은 스택과 재귀함수로 구현할 수 있는데 저는 재귀함수 부분이 어려워서 하면서 공부하고자 DFS를 재귀함수로 구현해보았습니다.
✅ 노드방문을 알아보는 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 노드방문 {
static int N,E; // N은 노드의 수, E는 엣지(간선)의 수
static int[][] Graph; // 그래프를 표현할 2D 배열
static boolean[] Visited; // 각 노드의 방문 여부를 저장할 배열
// 재귀함수로 구현한 DFS
static void dfs(int node) {
Visited[node] = true; // 현재 노드를 방문했다고 표시
System.out.println(node + " "); // 현재 노드 출력
// 인접 노드를 순회
for(int next=0; next<N; ++next ) {
// 아직 방문하지 않은 노드이며, 간선이 존재한다면
if(!Visited[next] && Graph[node][next] != 0 ) {
dfs(next); // 해당 노드로 DFS 진행
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
// N과 E를 입력 받음
N = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
// 그래프와 방문 배열 초기화
Graph = new int[N+1][N+1];
Visited = new boolean[N+1];
// 간선 정보를 입력 받음
for(int i=0; i<E; ++i) {
st = new StringTokenizer(bf.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
// 양방향 간선으로 그래프를 설정
Graph[u][v] = Graph[v][u] = 1;
}
// 노드 0부터 DFS 시작
dfs(0);
}
}
위의 그림과는 다르게 코드에서 입력은
이와 같은 상태를 두고 구현했습니다.
( 노드 5개 , 엣지 6개 구성 )
입력
5 6 // 노드5개, 엣지6개
0 1
0 2
1 3
1 4
2 4
3 4
출력(탐색순서)
0
1
3
4
2
📝 추가 문제
📎 백준 2606번 - 바이러스
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class 바이러스 {
static ArrayList<Integer>[] A;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
int E = Integer.parseInt(bf.readLine());
A = new ArrayList[N + 1];
visited = new boolean[N + 1];
for (int i = 1; i < N + 1; i++) {
A[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
StringTokenizer st = new StringTokenizer(bf.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
A[u].add(v);
A[v].add(u);
}
System.out.println(dfs(1)-1);
}
static int dfs(int node) {
if(visited[node]) {
return 0;
}
visited[node] = true;
int count = 1;
for(int i : A[node]) {
if(visited[i] == false) {
// dfs(i) 의 반환한 개수를 count 에 누적
count += dfs(i);
}
}
return count;
}
}