DFS (Depth First Search)

DFS(Depth First Search)는
한 경로를 끝까지 탐색한 뒤 되돌아오는 탐색 알고리즘이다.

즉, 갈 수 있는 곳까지 계속 들어가고
막히면 이전 지점으로 돌아와 다른 경로를 탐색한다.

예를 들어 미로를 탐색할 때,
갈 수 있는 길 → 계속 이동
막다른 길 → 뒤로 돌아가기
다른 길 탐색
이 방식이 DFS이다.

 

DFS 특징

- 깊게 탐색
- 모든 경우 탐색 가능
- 백트래킹 구조
- 재귀 사용이 일반적

 

언제 DFS를 사용?

- 모든 경우의 수 탐색
- 경로 찾기
- 조합 문제
- 퍼즐 문제
- 그래프 탐색
- 연결 요소 찾기

function dfs(node) {
    // 현재 노드 처리

    for (const next of neighbors) {
        dfs(next);
    }
}

 

 

DFS의 기본 구조이다.

DFS 시간복잡도

보통

O(V + E)

(V = 노드 수, E = 간선 수)

경우의 수 문제에서는

O(2^N)

 

DFS 장점

- 구현이 간단
- 모든 경로 탐색 가능
- 재귀로 표현 쉬움

DFS 단점

- 깊이가 깊으면 스택 오버플로우 가능
- 최단 거리 문제엔 비효율적

---

보통 문제에서

- 모든 경우
- 탐색
- 경로
- 조합
- 선택

이런 표현들이 나오면 DFS를 의심해 봐야 한다.

 

프로그래머스 Lv.2 - 타겟 넘버

function solution(numbers, target) {
    var answer = 0;
    // 재귀함수
    // 한쪽은 +, 한쪽은 -
    function dfs(index, sum) {
        if (index == numbers.length) {
            if (target == sum) answer++;
            return
        }
        
        dfs(index + 1, sum + numbers[index]) // +
        dfs(index + 1, sum - numbers[index]) // -
    }
    
    dfs(0, 0) // dfs 시작
    
    return answer;
}

numbers 배열의 숫자들에
+ 또는 -를 붙여서
target이 되는 경우의 수를 구하는 문제이다.

모든 숫자들에 +, -를 붙여보며 모든 조합을 탐색해야 한다.

→ DFS 문제!

dfs 함수는 현재 상태를 나타내는 함수이다.
- index: 몇 번째 숫자까지 봤는지
- sum: 현재까지 계산된 합

예를 들어 number가 [1, 2, 3]라고 한다면,

dfs(0, 0)

→ dfs(1, 0+1) = dfs(1, 1)
→ dfs(1, 0-1) = dfs(1, -1)

dfs(1, 1)
→ dfs(2, 1+2) = dfs(2, 3)
→ dfs(2, 1-2) = dfs(2, -1)

dfs(1, -1)
→ dfs(2, -1+2) = dfs(2, 1)
→ dfs(2, -1-2) = dfs(2, -3)
...

이렇게 모든 경우의 수를 다 볼 수 있게 된다.

프로그래머스 Lv.3 - 네트워크

function solution(n, computers) {
    let count = 0;
    const visited = new Array(n).fill(false);

    function dfs(node) {
        visited[node] = true;

        for (let i = 0; i < n; i++) {
            if (computers[node][i] === 1 && !visited[i]) {
                dfs(i);
            }
        }
    }

    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
            count++;
        }
    }

    return count;
}

이 문제는 visited 배열이 핵심이다.

그래프 덩어리 개수를 구하는 것이 핵심이기 때문에, 
하나의 노드에서 DFS로 쭉 타고 가면 그 노드와 연결된 모든 노드를 방문할 수 있게 된다.

👉 한 번 DFS 실행 = 네트워크 1개 찾은 것

그렇기 때문에 방문한 노드는 다시 방문하지 않는 것이 중요하다.
이럴 때 쓰이는 게 visited 배열.

const visited = new Array(n).fill(false);

길이가 n이고 false로 채워진 visited 배열

dfs 함수

function dfs(node) {
    visited[node] = true;

dfs 실행을 하면 node 방문 처리!

for (let i = 0; i < n; i++) {
    if (computers[node][i] === 1 && !visited[i]) {
        dfs(i);
    }
}

연결된 노드 탐색

- 현재 node와 연결되어 있고
- 아직 방문하지 않았다면
- 그 노드로 이동!

for (let i = 0; i < n; i++) {
    if (!visited[i]) {
        dfs(i);
        count++;
    }
}

예를 들어

0 - 1
2 - 3

이렇게 되어있다면, 0에서 DFS 돌렸을 때 0, 1을 방문하게 된다.
그러면 2, 3을 아직 방문을 못했으니

- 방문 안 된 노드 발견
- 새 DFS 시작
- count++

👉 새 DFS 시작 = 새로운 네트워크 발견