8주차
Depth-First Search의 줄임말로 깊이 우선 탐색을 말한다.
루트 노드 (또는 시작 노드)에서 시작해서 다음 분기 (branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법!
- 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없으면 가장 가까운 갈림길로 다시 돌아와 다른 방향으로 다시 탐색 진행하는 방법과 유사
- 모든 노드를 방문하고자 할 때 활용
- 재귀문 또는 반복문과 스택으로 구현 가능
- 어떤 노드를 방문했는지 검사 필수 -> 검사 안하면 무한루프 가능성 있음
👍 장점
- BFS보다 구현 간단
- 현 경로 상의 노드만 기억하면 되므로 저장공간 수요 비교적 적음
- 목표 노드가 깊이 있을 경우 해를 빨리 구할 수 있음
👎 단점
- 해가 없는 경로가 깊으면 탐색 시간 길어짐
- 최단 경로로 해를 얻는다는 보장 없음
- 최적 해라는 보장 없음
- 깊이가 무한히 깊어지면 스택 오버플로우 위험
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)
const graph = {
A: ['B', 'C'],
B: ['D', 'E'],
C: ['F'],
D: [],
E: ['F'],
F: []
};// visited : 방문한 노드를 기록하는 집합
function dfsRecursive(graph, start, visited = new Set()) {
// 현재 노드를 출력 후 방문 처리
console.log(start);
visited.add(start);
// 현재 노드의 이웃을 순서대로 확인
for (let neighbor of graph[start]) {
// 미방문 노드면 재귀 호출로 깊이 탐색
if (!visited.has(neighbor)) {
dfsRecursive(graph, neighbor, visited);
}
}
}
dfsRecursive(graph, 'A');function dfsStack(graph, start) {
// 스택에 시작 노드 (A) 넣고 시작
const stack = [start];
// visited로 방문 기록
const visited = new Set();
// 스택이 빌 때까지 반복
while (stack.length > 0) {
// pop()으로 가장 마지막에 넣은 노드 꺼냄
const node = stack.pop();
// 꺼낸 노드가 미방문이면 출력 후 방문 처리
if (!visited.has(node)) {
console.log(node);
visited.add(node);
// 이웃 노드들을 역순으로 스택에 넣음
// 역순으로 넣어야 원래 순서대로 꺼낼 수 있음
for (let neighbor of [...graph[node]].reverse()) {
stack.push(neighbor);
}
}
}
}
dfsStack(graph, 'A');- 연결 요소 개수
- 특정 노드에서 도달 가능한 노드 탐색
- 방문 배열 관리
- 상하좌우 탐색으로 영역 개수 세기
- 영역 크기 구하기
- 방향 배열 고정 패턴
- 전위/중위/후위 순회
- 깊이 계산
- 부모 노드 추적
- 부모 파라미터 전달
- 깊이 관리
- 모든 경우의 수 탐색
- 조합/순열 생성
- 조건 만족 여부 확인
- append -> dfs -> pop 구조로 가지치기
- 방문 상태 관리
- 현재 경로에 있는 노드를 다시 만나면 사이클 존재
class Solution {
int answer = 0;
public int solution(int[] numbers, int target) {
dfs(numbers, target, 0, 0);
return answer;
}
private void dfs(int[] numbers, int target, int idx, int sum) {
if (idx == numbers.length) {
if (sum == target) answer++;
return;
}
dfs(numbers, target, idx + 1, sum + numbers[idx]);
dfs(numbers, target, idx + 1, sum - numbers[idx]);
}
}def solution(numbers, target):
answer = 0
def dfs(idx, current):
nonlocal answer
if idx == len(numbers):
if current == target:
answer += 1
return
dfs(idx + 1, current + numbers[idx])
dfs(idx + 1, current - numbers[idx])
dfs(0, 0)
return answerfunction solution(numbers, target) {
let answer = 0;
function dfs(idx, sum) {
if (idx === numbers.length) {
if (sum === target) answer++;
return;
}
dfs(idx + 1, sum + numbers[idx]);
dfs(idx + 1, sum - numbers[idx]);
}
dfs(0, 0);
return answer;
}시작: dfs(0, 0)
- 아무 숫자도 사용하지 않았고 합계도 0
첫 번째 숫자 (1)
- dfs(1, 0+1)
- dfs(1, 0-1)
두 번째 숫자 (2)
- dfs(2, 1+1)
- dfs(2, 1-1)
- dfs(2, -1+1)
- dfs(2, -1-1)
이런 식으로 반복하며 탐색
마지막 인덱스에 도달했을 때 합계가 목표값이면 answer++
- 방문한 노드를 다시 방문해서 무한 루프 발생
-> 방문 여부를 DFS 시작 시점에 기록
- 재귀가 중간에 멈추거나 끝없이 호출됨
-> 종료 조건을 명확히 설정
- DFS는 깊이 우선이라 최단 경로를 보장하지 않음
-> 최단 거리 문제는 BFS 사용