깊이우선탐색이라고도 불린다. 그래프를 넓게 탐색하기 보다는, 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
DFS의 구체적인 동작과정은 다음과 같다.
*'방문처리'는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는것을 의미. 방문처리를 함으로써 각 노드를 한번씩만 처리할 수 있다.
DFS는 스택 자료구조에 기초하며, 탐색을 수행함에 있어서 시간복잡도가 O(N)이 소요된다. 스택을 이용해서 DFS를 구현할 수 있지만, 재귀함수를 사용하면 코드를 더 간결하게 사용할 수 있다.
package DFS_BFS;
import java.util.Stack;
public class StackDFS {
// 방문처리 배열
static boolean[] visited = new boolean[9];
// 그래프의 연결상태를 2차원 배열로 표현
// 인덱스가 각각의 노드번호가 되고 0번 인덱스는 아무것도 없는 상태
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) {
// 시작노드 1을 스택에 넣어주고 방문처리 해줌
stack.push(1);
visited[1] = true;
// 스택에 더이상 값이 없을때까지 반복
while(!stack.isEmpty()) {
//스택에서 값 꺼냄
int nodeIndex = stack.pop();
System.out.println(nodeIndex + " -> ");
//꺼낸 노드와 인접한 노드 순회
for(int LinkedNode : graph[nodeIndex]) {
//방문처리 안된노드는 스택에 넣고 방문처리
if(!visited[LinkedNode]) {
stack.push(LinkedNode);
visited[LinkedNode] = true;
}
}
}
}
}
package DFS_BFS;
public class RecursionDFS {
// 방문처리에 사용할 배열
static boolean[] visited = new boolean[9];
// 그래프의 연결상태를 2차원 배열로 표현
// 인덱스가 각각의 노드번호가 되고 0번 인덱스는 아무것도 없는 상태
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 nodeIndex) {
// 해당 노드 방문처리
visited[nodeIndex] = true;
System.out.print(nodeIndex + " - > ");
// 해당 노드에 인접한 노드 순회
for(int node : graph[nodeIndex]) {
//인접한 노드중 방문처리 안된게 있다면 재귀호출
if(!visited[node]) {
dfs(node);
}
}
}
}
참고자료
나동빈, 「이것이 코딩테스트다」
소스코드 : [Algorithm] DFS (Depth-first Search)를 Java로 구현해보자!