TIL_20250315_dfs

📌 TIL: DFS를 활용한 삼총사 문제 해결

그동안 쉬운 알고리즘만 풀다가 오랜만에 기법을 쓰는 알고리즘을 푸니 가물가물하다. 매일매일 풀 거니 확실하게 정리하고 가자! 🚀

---

📌 문제 분석

number 배열에서 3명의 학생을 선택했을 때, 합이 0이 되는 경우의 수를 구하는 문제이다.

• 단순한 for 루프(O(N³))로 풀 수도 있지만,
• 백트래킹(DFS)을 활용하여 조합 탐색을 최적화할 수도 있다.

---

1️⃣ DFS를 활용한 접근 방법

DFS를 활용하여 3명의 학생을 조합을 탐색하고, 합이 0인지 체크하는 방식으로 문제를 해결할 수 있다.

✅ 핵심 로직

1. 학생 3명을 선택할 때까지 재귀 호출 (count == 3이면 종료)
2. 합이 0인지 체크하고 정답 개수 증가
3. 백트래킹을 통해 다음 조합을 탐색

---

2️⃣ 구현한 코드

class Solution {
    int answer = 0; // 정답 개수 저장

    public int solution(int[] number) {
        dfs(number, 0, 0, 0); // 초기 DFS 호출 (인덱스 0부터 시작)
        return answer;
    }

    public void dfs(int[] number, int index, int count, int sum) {
        if (count == 3) { // 학생 3명을 선택한 경우
            if (sum == 0) answer++; // 합이 0이면 정답 증가
            return;
        }

        for (int i = index; i < number.length; i++) { // 현재 인덱스부터 탐색
            dfs(number, i + 1, count + 1, sum + number[i]); // 다음 조합 탐색
        }
    }
}

---

3️⃣ DFS 실행 흐름

number = {-2, 3, 0, 2, -5} 가 주어졌을 때, DFS가 탐색하는 방식은 다음과 같다.

DFS(0, 0, 0)
 ├─ DFS(1, 1, -2)
 │   ├─ DFS(2, 2, 1)
 │   │   ├─ DFS(3, 3, 1) → X (sum != 0)
 │   │   ├─ DFS(4, 3, -4) → X (sum != 0)
 │   │
 │   ├─ DFS(3, 2, -2)
 │   │   ├─ DFS(4, 3, 0) → ✅ 정답 1
 │   │
 │   ├─ DFS(4, 2, -7)
 │
 ├─ DFS(2, 1, 3)
 │   ├─ DFS(3, 2, 3)
 │   │   ├─ DFS(4, 3, 0) → ✅ 정답 2

💡 정답: (첫 번째, 세 번째, 네 번째) / (두 번째, 네 번째, 다섯 번째) 조합 2개 발견!

---

4️⃣ DFS vs 삼중 for문 비교

다른 사람들의 풀이를 보니 3중 for문이 압도적으로 많고,
bfs & combination을 구현한 사람도 있었다.

조건이 없는 경우 & 수행 횟수가 적은 경우에는 3중 for문이 효율적인게 살짝 충격이었다.

방법	시간 복잡도	장점	단점
DFS (현재 코드)	O(2^N) ≈ O(N³)	유연한 탐색 가능	스택 오버헤드 발생 가능
삼중 for 루프	O(N³)	가장 빠름, 단순함	확장성이 낮음

🚀 결론

1️⃣ 이 문제에서는 for 루프가 더 빠르지만,
2️⃣ DFS는 조합을 찾을 때 활용할 수 있는 중요한 기법이므로 확실히 익혀야 한다!

---

5️⃣ 오늘의 배운 점

✅ DFS로 조합을 찾을 때는 index를 증가시키면서 중복 선택을 방지해야 한다.
✅ 백트래킹을 활용하면 모든 경우를 탐색하는 문제가 쉽게 해결된다.
✅ 삼중 for 루프가 가능할 때는 for를 쓰는 것이 더 빠르다.

🎯 내일은 DFS + 백트래킹을 활용한 다른 조합 문제를 풀어보자! 🚀