DFS Depth-First Search
- 깊이우선탐색 : child의 마지막 노드를 만날 때까지 순회한다
- Stack으로 구현
- 루트 노드를 맨 처음 넣고 자식노드와 자식의 자식노드를 추가한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
static int M;
static int[] arr = new int[M];
public static void dfs(int depth) {
//재귀 깊이가 M과 같아지면 탐색과정에서 담았던 배열을 출력
if (depth == M) {
for (int val : arr) {
System.out.println(val + " ");
}
System.out.println();
return;
}
for (int i = 0; i < N; i++) {
//만약 해당 노드를 방문하지 않았다면
if (isVisited[i] == false) {
//해당 노드를 방문 상태로 변경
isVisited[i] = true;
//해당 깊이를 index로 하여 i+1값 저장
arr[depth] = i + 1;
//다음 자식 노드 방문을 위해 depth를 1씩 증가시키면서 재귀 호출
dfs(depth + 1);
//자식노드 방문이 끝나고 돌아오면 방문노드를 방문하지 않은 상태로 변경
isVisited[i] = false;
}
}
return;
}
BFS Breath-First Search
- 넓이우선검색 : 같은 depth의 child들을 먼저 순회한 뒤 다음 depth의 child 노드를 방문한다. 레벨 단위
- Queue로 구현
reference
[백준] 15649번 : N과 M (1) - JAVA [자바] [자료구조 알고리즘] Graph 검색 DFS, BFS 구현 in Java
