[JAVA] 알고리즘 DFS [Depth-First Search] 깊이 우선 탐색
DFS [Depth-First Search]는 깊이 우선 탐색이며 깊이를 우선적으로 탐색합니다.
2차원 배열이나 그래프 탐색에서 한번 방문한 노드는 다시 방문하지 않으며 깊이 탐색을 통해 방문하여 모든 노드를 탐색하는 방법입니다.
BFS와 마찬가지로 모든 노드를 탐색하는 방법 중 하나입니다.
- DFS - 재귀, stack 자료 구조 활용
- BFS - Queue 자료 구조 활용
DFS를 코드로 구현하기 위해선 3가지가 필요합니다.
- 탐색할 2차원 배열 또는 그래프
- 방문처리를 하기 위한 boolean type
- Stack 자료 구조 또는 재귀 함수
|
1
2
|
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}}; // 그래프
|
cs |
방문체크를 위한 boolean 배열과 그래프를 선언합니다.
추가로 Stack 자료 구조를 활용하기보다는 재귀 함수를 통해서 구현해보도록 하겠습니다.
이제 깊이 탐색을 위한 DFS함수를 작성해봅시다.
|
1
2
3
4
5
6
7
8
9
|
public static void dfs(int x) {
visited[x] = true;
sb.append(x).append(" "); // StringBuilder 방문 순서 결과를 보기 위해 사용
for (int i = 0; i < graph[x].length; i++) {
if (!visited[graph[x][i]]){
dfs(graph[x][i]);
}
}
}
|
cs |
가장 먼저 DFS의 매개변수로 들어온 int x 노드부터 깊이 탐색을 진행합니다.
x 노드를 다시 방문하지 않도록 방문처리를 가장 먼저 처리해주도록 하겠습니다.
x 노드와 연결된 노드들을 확인하기 위해 for (int i = 0; i < graph [x]. length; i++) 반복문을 사용하여
x 노드와 연결된 모든 노드들을 확인해줍니다.
반복을 통해 하나씩 확인해가며 if (! visited [graph [x][i]])를 이용하여 이미 방문이 돼있다면 true,
방문하지 않았다면 false 이므로 방문하지 않아야만 재귀 함수를 통해 해당 노드를 DFS 인자로 넣은 후 호출해줍니다.
여기서 생각해야 할 점은 재귀 함수를 호출하여 제어를 넘겨주었으므로
for 반복문은 재귀 함수가 완전히 처리된 이후에 다시 제어를 얻어 진행하던 반복을 진행하게 됩니다.
호출한 함수가 완료되야 제어를 얻어 다음 노드로 반복을 진행하게 됩니다.
이러한 재귀 함수를 이용하는 점이 바로 Stack 자료 구조 방식으로 깊이 탐색을 가능하도록 해줍니다.
간단하게 말하자면, 해당 dfs함수에서 재귀함수를 호출하면 현재 진행하는 반복이 멈춘후 재귀함수를 먼저 진행한다. 라고 생각하시면 됩니다.
전체 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class DFS_graph {
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}};
static StringBuilder sb = new StringBuilder();
public static void dfs(int x) {
visited[x] = true;
sb.append(x).append(" ");
for (int i = 0; i < graph[x].length; i++) {
if (!visited[graph[x][i]]){
dfs(graph[x][i]);
}
}
}
public static void main(String[] args) {
dfs(1);
System.out.println(sb);
}
}
|
cs |
'CS > 알고리즘' 카테고리의 다른 글
| 코딩테스트 자료구조, 알고리즘 정리 (0) | 2022.06.16 |
|---|---|
| [알고리즘] Binary Search 이분탐색 - JAVA (0) | 2022.06.09 |
| [알고리즘] 다익스트라 최단 경로 알고리즘 (Dijkstra Algorithm) (0) | 2022.04.20 |
| [알고리즘] 플로이드 워셜 알고리즘 (Floyd Warshall Algorithm) (0) | 2022.04.17 |
| [JAVA] 알고리즘 BFS[Breadth-First Search] 너비 우선 탐색 (1) | 2022.03.16 |