[알고리즘] 깊이 우선 탐색(DFS)
2020. 8. 1.
그래프 탐색 그래프 탐색은 하나의 노드에서 시작하여 모든 노드를 차례로 한 번씩 방문한다. 깊이 우선 탐색(Depth First Search : DFS) DFS는 그래프 탐색 중 하나로 루트 노트 또는 정해진 노드로부터 시작하여 최대한 깊이 탐색한 후 더 이상 갈 곳이 없으면 다시 원점으로 돌아와 다른 루트를 탐색하는 방식이다. 모든 노드를 방문하고자 할 경우 이 방법을 선택하고, 스택 또는 재귀함수를 통해 구현한다. 너비 우선 탐색(BFS)보다는 간단하지만 검색 속도가 비교적 느리다. 예제 코드 public class DfsExam1 { static int T; // 테스트 케이스 static int N; // 조합하고자 하는 숫자, 경우의 수 static int visited[] = new int[7..
