깊이 우선 탐색 알고리즘 (DFS Algorithm)

탐색 알고리즘 문제를 볼때마다 멍해지는 관계로 이번 기회에 확실히 짚고 넘어가야겠다. 이번 포스트에서는 DFS를 정리한다.

---

DFS (Depth-first search)

미로 문제 해결 전략으로 연구된 DFS는 트리 및 그래프 구조를 탐색하는 알고리즘 기법이다. 트리의 경우엔 root node부터, 그래프의 경우엔 임의의 node부터 맨 밑까지 탐색하면 되고, 이전에 방문한 노드는 다시 방문하지 않는다. 그림으로 표현하면 아래와 같다.

출처: https://en.wikipedia.org/wiki/Depth-first_search

일반적으로 DFS 알고리즘은 그래프 전체를 탐색하는데 사용한다. 시간 복잡도는 O(|V|+|E|)으로 그래프 사이즈만큼의 선형 시간이 걸린다. (V는 정점의 수, E는 간선의 수를 나타낸다) 즉, 정점이 늘어나는만큼 시간도 오래 걸리기 때문에, 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)을 사용한다. 스택 또는 재귀 함수로 구현할 수 있으며 재귀 함수를 이용해 프로그래머스의 타겟 넘버 문제를 풀어봤다. https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

function solution(numbers, target) {
    var answer = 0;
    let index = 0, calc = 0;
    
    const dfsRecursion = (i, sum) => {
    	// numbers 배열의 끝까지 다다르지 않았다면
        if(i < numbers.length){
            // 재귀함수 실행
            dfsRecursion(i + 1, sum+numbers[i]);
            dfsRecursion(i + 1, sum-numbers[i]);
        }else{
            return sum === target ? answer++ : answer;    
        }
    }
    
    dfsRecursion(index, calc);
    return answer;
}

1. 탐색 구간을 모두 순환할 수 있도록 범위를 정해주고
2. 마지막 노드(범위 끝)에 다다르기 전까지 재귀함수로 반복
3. 마지막 노드(범위 끝)에 다다르면 찾고자하는 값과 계산한 값이 동일한지 확인
   현재 재귀 함수에서 return을 하게 되면, call stack의 맨 위 함수가 빠지게 되어 바로 직전의 함수로 돌아가고, 해당 함수는 스코프에 당시의 상태를 기억해놓기 때문에 모든 경우를 탐색할 수 있다.

 

이번에는 스택을 활용해 DFS 알고리즘을 구현했다. 문제는 프로그래머스의 네트워크이다. https://programmers.co.kr/learn/courses/30/lessons/43162?language=javascript

코딩테스트 연습 - 네트워크

function solution(n, computers) {
    let answer = 0;
    let i = 0, count = 0, check = [], stack = [];
    
    while(count < n){
        for(let j = 0; j < n; j++){
            // 특정 컴퓨터가 check에 포함되지 않았다면
            if(computers[i][j] === 1 && !check.includes(j)){
                // stack에 해당 컴퓨터의 인덱스를 쌓는다
                stack.push(j);
                // check에 해당 컴퓨터의 인덱스를 저장한다
                check.push(j);
            };
        };
        // 만약 stack에 값이 있을 경우
        if(stack.length > 0){
            // stack의 맨 위 값을 변수 i에 할당하고
            i = stack.pop();
        }
        // stack이 비었다면
        if(stack.length === 0){
            // 특정 컴퓨터와 관련된 컴퓨터를 모두 탐색했으므로 하나의 네트워크를 찾은 것
            answer++;
            // i를 0으로 초기화시키고
            i = 0;
            // check에 저장되지 않은 값이 될 때까지 i에 1씩 더하기
            while(check.includes(i)){
                i++;
            }
        }
        // 네트워크의 최대 개수 <= 컴퓨터 개수이므로 count가 컴퓨터 수(n)보다 작을때까지 반복
        // (변수 count를 선언할 때 0을 할당했으므로 n 미만일때까지 반복)
        count++;
    }
    return answer;
}

 

 

>> DFS 알고리즘은 언제 사용해야되고 장단점은 뭘까? <<

 

DFS를 사용하는 경우

• 모든 경우의 수를 탐색할 때 활용

장점

• BFS에 비해 메모리 사용이 적다  → 백트랙킹할 노드만 저장하면 됨
• BFS에 비해 구현이 쉽다

단점

• 그래프/트리가 깊을수록 탐색시간이 오래걸리고, 찾은 경로가 최적의 경로가 아닐 수 있다
• BFS에 비해 속도가 느리다

 

 

 

---

참고 문서

• https://en.wikipedia.org/wiki/Depth-first_search
• https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html