DFS는 Depth First Search의 약자로, 깊이 우선 탐색이라고도 부르며 그래프 순회 방법 중 하나이다.
순회 방식은, 시작 노드에서 깊이가 커지는 방향으로 탐색을 진행하여 더 이상 방문할 인접 노드가 없는 경우, 이전 노드로 돌아가서, 다시 깊이 우선 탐색을 반복하는 방식이다.
위의 그래프를 예를 들어 DFS 탐색을 시작해보겠다.
(탐색 순서 : 1)
(탐색 순서 : 1 → 2)
(탐색 순서 : 1 → 2 → 6)
(탐색 순서 : 1 → 2 → 6 → 8)
(탐색 순서 : 1 → 2 → 6 → 8 → 3)
(탐색 순서 : 1 → 2 → 6 → 8 → 3 → 5)
(탐색 순서 : 1 → 2 → 6 → 8 → 3 → 5 → 4)
최종적인 탐색 순서는 다음과 같다.
(탐색 순서 : 1 → 2 → 6 → 8 → 3 → 5 → 4 → 7)
DFS를 코드로 구현하는 방법은 재귀로 구현하는 방법과 Stack을 사용해서 구현하는 방법 2가지가 있다.
일반적으로, Stack 보다는 재귀로 구현하는 게 코드가 더 짧고 간결하기 때문에, 재귀로 많이 구현을 한다.
import java.util.*;
public class Main {
static int edge; // 간선의 수
static int vertex; // 정점의 수
static int[][] map; // 정점 간의 연결의 정보를 담는 객체
static boolean[] visit; // 정점을 방문했는지 체크하기 위한 객체
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
vertex = sc.nextInt();
edge = sc.nextInt();
map = new int[vertex + 1][vertex + 1];
visit = new boolean[vertex + 1];
for (int i = 0; i < edge; i++) {
int start = sc.nextInt();
int next = sc.nextInt();
map[start][next] = 1;
map[next][start] = 1;
}
dfs(1);
}
public static void dfs(int start) {
visit[start] = true;
System.out.println(start + " ");
for (int i = 1; i < vertex + 1; i++) {
if (map[start][i] == 1 && visit[i] == false) {
dfs(i);
}
}
}
}
🤔오호오호