BFS, DFS
너비 우선 탐색(BFS; Breadth-First Search)과 깊이 우선 탐색(DFS; Depth-First Search)은 그래프 또는 트리 구조에서 모든 정점을 방문하는 대표적인 탐색 방법이다.

BFS는 루트(시작 정점)의 자식 노드들을 먼저 방문한 후, 그 자식들의 자식을 방문하는 식으로 진행한다. 즉, 루트에서 가까운 정점부터 차례대로 방문하므로 거리 순으로 탐색한다.

DFS는 루트의 자식 중 하나를 선택하여 끝까지 내려간 후, 더 이상 내려갈 곳이 없으면 다시 위로 되돌아오며 다른 경로로 내려가는 방식이다. 즉, 한 경로를 깊게 탐색한 후 다른 경로를 탐색하는 백트래킹(Backtracking) 방식이다.

DFS

DFS는 백트래킹을 기반으로 하며, 탐색 도중 막히면 한 단계씩 되돌아가 다른 경로를 탐색한다. 주로 재귀 함수 또는 스택을 사용하여 구현한다.

탐색과정은 아래와 같다.

1. 탐색을 시작한 정점을 방문 처리한다.

2. 연결된 정점들 중 아직 방문하지 않은 곳으로 이동한다.

3. 더 이상 진행할 수 없으면 이전 정점으로 돌아가 다른 경로를 찾는다.

4. 이 과정을 통해 모든 정점을 방문할 때까지 반복한다.

DFS 알고리즘

DFS(v)
{
	visited[v] ←YES;
    for each x ∈ L(v)	// L(v) : 정점 v의 인접 정점 집합
    	if(visited[x]=NO) then DFS(x);
}

• 정점 v에 대해 DFS(v)를 호출하면, 먼저 v를 방문 처리하고, v와 인접한 정점들 중 아직 방문하지 않은 정점 x에 대해 재귀적으로 DFS(x)를 호출한다.

• 이 과정에서 정점 v의 인접 정점 중 일부는 재귀 호출을 통해 다른 경로로 먼저 방문될 수 있으므로, 재방문을 막기 위해 visited 배열을 사용한다

DFS의 시간 복잡도

DFS의 시간 복잡도는 Θ(V + E) 이다.

• V: 정점의 수
• E: 간선의 수

모든 정점을 한 번씩 방문하며, 각 간선을 한 번씩 확인하기 때문에 전체 시간 복잡도는 선형이다.

피로도 문제

아래는 깊이 우선 탐색(DFS)을 사용하여 탐험할 수 있는 최대 던전 수를 구하는 Java 코드 예시이다.
이 문제는 방문 순서의 모든 경우의 수를 탐색해야 하므로 DFS를 활용하며, 탐색 도중 백트래킹(backtracking) 을 사용하여 상태를 복원한다.

문제 조건 요약

• 현재 피로도 k가 각 던전의 최소 필요 피로도 이상이어야 입장 가능하다.
• 던전에 입장하면 피로도가 감소한다.
• 한 번 방문한 던전은 다시 방문할 수 없다.
• 가장 많이 방문할 수 있는 던전의 수를 구하라.

class Solution {
    public int solution(int k, int[][] dungeons) {
        boolean[] visited = new boolean[dungeons.length];
        return dfs(k, 0, visited, dungeons);
    }
    
    public int dfs(int k, int cnt, boolean[] visited, int[][] dungeons) {
        int answer = cnt;
        for (int i=0; i<dungeons.length; i++) {
            if(k>=dungeons[i][0] && !visited[i]) { // 피로도가 충분하고 방문한 적 없다면
                visited[i] = true;  // 방문
                int a = dfs(k-dungeons[i][1], cnt+1, visited, dungeons);    // 다음 던전 방문
                answer = Math.max(answer, a);
                // 방문에 실패할 경우
                visited[i] = false; // backtracking
                
            }
        }
        return answer;
    }
}

타겟넘버

class Solution {
    int count = 0;
    public int solution(int[] numbers, int target) {
        dfs(numbers, 0, 0, target);
        return count;
    }
    
    void dfs(int[] numbers, int depth, int sum, int target) {
        if (depth == numbers.length) {
            if (sum == target) count++;
            return;
        }

        dfs(numbers, depth + 1, sum + numbers[depth], target); // + 선택
        dfs(numbers, depth + 1, sum - numbers[depth], target); // - 선택
    }
}