[알고리즘/JAVA] DFS(깊이 우선 검색, Depth First Search)
DFS는 한 놈만 패는 방식으로, 하위 레벨 노드를 쭉 탐색한 다음에 다른 옆 분기로 넘어가면서 텀색하는 방식이다.
BFS보다 느린 편이고, 스택 또는 재귀 방식으로 구현할 수 있다.
DFS는 경로의 특징(비용, 거리)등을 저장해야 하는 경우에 사용하며, BFS는 특징을 저장할 수 없다.
그림으로 DFS 이해하기
다음의 그래프를 통해서 DFS 방식을 이해하도록 한다.
1. 오름 차순으로 탐색한다고 가정하면, 1번 노드를 먼저 방문처리하고 출력한다.
그리고 1번과 연결된 2,5,8 노드 중에서 2번 노드, 한놈만 파도록 한다.
2. 2번 노드를 방문처리하고 출력한다. 그리고 2번 노드와 연결된 노드인 6,8번 노드 중에서 작은 노드인 6번를 먼저 탐색한다.
3. 6번 노드를 방문처리 하고 출력한다. 6번 노드와 연결된 노드 중에서 방문한 노드는 없다.
따라서 다시 다시 2번 노드의 연결된 노드 중에서 방문하지 않은 노드인 8번 노드를 탐색한다. 8번 노드를 방문처리하고 출력한다. 8번 노드와 연결된 노드 중에서 방문처리되지 않은 노드는 없으니, 다시 1번 노드로 올라와서 방문하지 않는 노드를 찾는다.
4. 1번 노드와 연결된 노드 중에서 방문하지 않은 노드는 3번 노드 뿐이다. 3번 노드를 방문처리하고 출력한다. 그리고 3번 노드와 연결된 노드 중에서 방문하지 않는 노드를 탐색한다.
5. 3번 노드와 연결된 노드 중에서 방문하지 않는 노드인 5번을 탐색한다. 5번 노드를 방문처리하고 출력한다.
그리고 5번와 연결된 노드 중에서 방문하지 않는 노드들을 탐색한다.
6. 5번와 연결된 노드 중에서 방문하지 않은 노드는 4,7번 노드이다. 이 중에서 작은 번호인 4번 노드를 방문처리하고 출력한다. 그리고 4번 노드와 연결된 노드 중에서 방문하지 않는 노드는 없으므로, 7번 노드를 탐색한다. 7번 노드를 방문처리하고 출력한다.
이제 더 이상 방문하지 않는 노드는 없다.
이 같은 방식은 재귀방식을 활용해서 DFS를 수행한 예시이다.
JAVA로 구현한 DFS (재귀방식)예시
public class dfs_recursion {
// 방문 처리에 사용할 visited 배열 선언
static boolean[] visited = new boolean[9]; // 9개 노드 가정
// 인덱스가 노드 번호 의미
// 0번 인덱스는 아무것도 없음
// 1번 노드는 2,3,8 노드과 연결되어 있고, 2번 노드는 1,6,8 노드와 연결되어 있음을 의미함
static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
public static void main(String[] args) {
dfs(1);
}
static void dfs(int start) {
// dfs 함수 접근하자마자, 방문 처리
visited[start]=true;
// 방문 처리한 노드는 출력
System.out.print(start + " -> ");
// 방문한 노드와 연결된 노드 중에서 방문하지 않은 노드를 탐색하도록 함
for (int i : graph[start]) { // 방금 방문 처리한 노드와 연결된 노드들만 대상으로 탐색함
if(!visited[i]) // 연결된 노드가 방문한 적이 없다면, dfs함수를 수행한다.
dfs(i); // 재귀방식으로 방문 처리하고, 해당 노드의 하위로 더 파보자!
}
}
}재귀방식으로 수행한 DFS의 결과는 다음과 같다.
1 -> 2 -> 6 -> 8 -> 3 -> 5 -> 4 -> 7 ->
JAVA로 구현한 DFS (Stack 방식)예시
import java.util.Stack;
public class dfs_stack {
// 방문처리 목적의 배열
static boolean visited[] = new boolean[9];
static int graph[][] = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
// DFS에 사용할 스택
static Stack<Integer> stack= new Stack<>();
public static void main(String[] args) {
// 시작 노드 입력
stack.push(1);
// 시작 노드 방문처리
visited[1] = true;
// 스택에 값이 없을 때까지 반복
while(!stack.isEmpty()) {
// 스택에서 값 1개 꺼내기
int node_out = stack.pop();
//방문노드 출력
System.out.print(node_out + "->");
// 인접노드 탐색
for(int i : graph[node_out]) {
if(!visited[i]) { // 방문한 적이 없다면
stack.push(i);
visited[i] = true;
}
}
}
}
}스택을 통해 DFS를 수행한 결과는 다음과 같습니다.
1->8->3->5->7->4->2->6->