8주차

DFS

개념

✨ DFS란?

Depth-First Search의 줄임말로 깊이 우선 탐색을 말한다.

💭 깊이 우선 탐색?

루트 노드 (또는 시작 노드)에서 시작해서 다음 분기 (branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법!

• 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없으면 가장 가까운 갈림길로 다시 돌아와 다른 방향으로 다시 탐색 진행하는 방법과 유사
• 모든 노드를 방문하고자 할 때 활용

✨ DFS의 특징

• 재귀문 또는 반복문과 스택으로 구현 가능
• 어떤 노드를 방문했는지 검사 필수 -> 검사 안하면 무한루프 가능성 있음

DFS 장/단점

👍 장점

• 현 경로 상의 노드만 기억하면 되므로 저장공간 수요 비교적 적음
• 목표 노드가 깊이 있을 경우 해를 빨리 구할 수 있음

👎 단점

• 해가 없는 경로가 깊으면 탐색 시간 길어짐
• 최단 경로로 해를 얻는다는 보장 없음
• 깊이가 무한히 깊어지면 스택 오버플로우 위험

✨ DFS 과정

트리 형태 그래프

1. 루트 노드 방문 (1)
2. 왼쪽 분기의 가장 깊이까지 하나씩 방문하며 내려감 (2, 3, 4)
3. 더 이상 내려갈 수 없으므로 경로를 되돌아가며 (백트래킹) 미방문 자식이 있는 노드 (3)에서 다시 탐색 (5)
4. 마찬가지로 백트래킹하며 미방문 자식이 있는 노드 (2)에서 다른 방향으로 탐색 (6)
5. 왼쪽 분기 탐색 완료 후 루트로 돌아와 다음 분기 탐색 (7)
6. 가운데 분기도 탐색이 끝났으므로 오른쪽 분기 타고 내려가며 탐색 (8, 9, 10)
7. 왼쪽과 동일하게 내려갈 수 없다면 백트래킹하며 미방문 노드 탐색을 반복 (11, 12)
8. 미방문 노드가 더 이상 없다면 탐색 종료

일반 그래프

1. 시작 점 방문 (A)
2. A의 분기 중 하나의 분기의 가장 깊이까지 하나씩 방문하며 탐색 (B, E, F, G)
3. 더 이상 갈 수 없으므로 백트래킹하며 미방문 이웃이 있는 노드 (F)에서 다른 방향으로 탐색 (C, D)

문제 패턴

예시 문제 기반 설명

Java

Python

JavaScript

실수 포인트