DFS

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

---

✅ DFS 문제 유형 + 기본 구현

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

---

📌 전제: adj는 인접 리스트

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 순회

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 순회

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

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

---

✅ ③ 연결 컴포넌트 수 세기

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 시간, 서브트리 크기, 깊이

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++;
}

📌 호출:

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

---

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

🔸 1) 경로가 존재하는지

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) 실제 경로 출력하기

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); // 백트래킹
}

📌 호출:

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

---

✅ 요약 정리

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

---

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