DFS(깊이 우선 탐색)
- 그래프 완전 탐색 기법 중 하나
- 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
- 특징 : 재귀 함수로 구현되며,(스택 오버플로에 유의) 스택 자료구조를 이용하기도 한다.
- 시간 복잡도는 O(V + E)이며, 여기서 V는 노드 수, E는 엣지 수를 말한다.
핵심 이론
- 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하다.
- 탐색 방식은 후입선출 특성을 가진다.
DFS 과정
- DFS를 시작할 노드를 정한 후 사용할 자료구조를 초기화한다.
- 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입한다.(방문 배열 체크)
- 스택 자료구조에 값이 없을 때까지 반복한다.
문제 풀이
https://yurison.tistory.com/548
[백준/자바] 11724 - 연결 요소의 개수
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { static ArrayList[] al; static boolean[] visited; public static void main(String[]
yurison.tistory.com
https://yurison.tistory.com/550
[백준/자바] 2023 - 신기한 소수
import java.util.Scanner; public class Main { static int N; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); dfs(2, 1); dfs(3, 1); dfs(5, 1); dfs(7, 1); sc.close(); } private static void dfs(int num, int targe
yurison.tistory.com
https://yurison.tistory.com/551
[백준/자바] 13023 - ABCDE
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { static boolean[] visited; static ArrayList[] arr; static boolean arrived; public
yurison.tistory.com
'공부 기록 > 알고리즘' 카테고리의 다른 글
| Do it! 알고리즘 코딩테스트 with JAVA - (15) 이진 탐색 (0) | 2023.08.07 |
|---|---|
| Do it! 알고리즘 코딩테스트 with JAVA - (14) BFS(너비 우선 탐색) (0) | 2023.08.07 |
| Do it! 알고리즘 코딩테스트 with JAVA - (12) 기수 정렬 (0) | 2023.08.03 |
| Do it! 알고리즘 코딩테스트 with JAVA - (11) 병합 정렬 (0) | 2023.08.03 |
| Do it! 알고리즘 코딩테스트 with JAVA - (10) 퀵 정렬 (0) | 2023.08.02 |
