# DFS

좋습니다! 이번엔 **DFS로 해결하는 그래프 문제 유형**을 정리하고,\
각 유형에 맞는 **기본 구현 코드**도 모두 제공해드릴게요.

***

### ✅ DFS 문제 유형 + 기본 구현

| 유형                                   | 설명                   |
| ------------------------------------ | -------------------- |
| ① 연결 그래프 DFS 순회                      | 정점 방문 순서 출력          |
| ② 비연결 그래프 전체 DFS                     | 모든 컴포넌트 방문           |
| ③ 컴포넌트 개수 세기                         | 연결된 그룹 수 세기          |
| ④ 트리 DFS (in/out 시간, 서브트리 크기, 깊이 계산) | 트리 전용                |
| ⑤ 경로 존재 여부 / 모든 경로 출력                | `start → end` DFS 탐색 |

***

#### 📌 전제: `adj`는 인접 리스트

```java
int n = 6;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

void addEdge(int u, int v) {
    adj.get(u).add(v);
    adj.get(v).add(u);  // 무방향
}
```

***

### ✅ ① 연결 그래프에서 DFS 순회

```java
void dfs(int v, boolean[] visited) {
    visited[v] = true;
    System.out.print(v + " ");
    for (int next : adj.get(v)) {
        if (!visited[next]) {
            dfs(next, visited);
        }
    }
}
```

📌 호출: `dfs(0, new boolean[n]);`

***

### ✅ ② 비연결 그래프 전체 DFS 순회

```java
void dfsDisconnected() {
    boolean[] visited = new boolean[n];
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, visited);
        }
    }
}
```

📌 여러 컴포넌트를 모두 방문

***

### ✅ ③ 연결 컴포넌트 수 세기

```java
int countComponents() {
    boolean[] visited = new boolean[n];
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            count++;
            dfs(i, visited);
        }
    }
    return count;
}
```

***

### ✅ ④ 트리 DFS: in/out 시간, 서브트리 크기, 깊이

```java
int[] in, out, size, depth;
int time = 0;

void dfsTree(int curr, int parent, int d) {
    in[curr] = time++;
    depth[curr] = d;
    size[curr] = 1;

    for (int child : adj.get(curr)) {
        if (child != parent) {
            dfsTree(child, curr, d + 1);
            size[curr] += size[child];
        }
    }

    out[curr] = time++;
}
```

📌 호출:

```java
in = new int[n]; out = new int[n]; size = new int[n]; depth = new int[n];
dfsTree(0, -1, 0);
```

***

### ✅ ⑤ 경로 존재 여부 / 경로 출력

#### 🔸 1) 경로가 존재하는지

```java
boolean found = false;

void dfsFind(int curr, int target, boolean[] visited) {
    if (curr == target) {
        found = true;
        return;
    }

    visited[curr] = true;
    for (int next : adj.get(curr)) {
        if (!visited[next]) {
            dfsFind(next, target, visited);
        }
    }
}
```

📌 호출: `dfsFind(start, end, new boolean[n]);` → `found == true` 확인

***

#### 🔸 2) 실제 경로 출력하기

```java
List<Integer> path = new ArrayList<>();
boolean foundPath = false;

void dfsPath(int curr, int target, boolean[] visited) {
    if (foundPath) return;
    visited[curr] = true;
    path.add(curr);

    if (curr == target) {
        foundPath = true;
        System.out.println("경로: " + path);
        return;
    }

    for (int next : adj.get(curr)) {
        if (!visited[next]) {
            dfsPath(next, target, visited);
            if (foundPath) return;
        }
    }

    path.remove(path.size() - 1); // 백트래킹
}
```

📌 호출:

```java
dfsPath(start, end, new boolean[n]);
```

***

### ✅ 요약 정리

| 유형     | 함수                  | 설명                     |
| ------ | ------------------- | ---------------------- |
| DFS 순회 | `dfs()`             | 방문 순서                  |
| 전체 순회  | `dfsDisconnected()` | 컴포넌트 포함 전체 탐색          |
| 컴포넌트 수 | `countComponents()` | 덩어리 수                  |
| 트리 분석  | `dfsTree()`         | in/out, depth, size 계산 |
| 경로 추적  | `dfsPath()`         | start → end 경로 출력      |

***

필요하시면 DFS 기반 **Topological Sort**, **사이클 탐지**, **백트래킹 퍼즐 탐색**, **트리 LCA** 확장도 도와드릴 수 있어요.
