[Algorithm] 깊이우선탐색 알고리즘 (DFS, Depth First Search Algorithm)

1. 깊이우선탐색(DFS, Depth First Search)

깊이 우선 탐색은 트리나 그래프를 탐색하는 방법 중 하나로,

깊이를 우선으로 하여 시작노드에서 자식노드까지 순서대로 탐색하는 알고리즘을 말한다. 

부분집합, 미로 풀기, 그래프에서 연결된 구성 요소 찾기, 퍼즐 풀기 등에서 사용된다.

 

재귀함수와 스택으로 비교적 쉽게 구현할 수 있으며, 후에 배울 BFS에 비해 메모리를 덜 사용한다.

 

그러나 재귀함수와 스택 자료구조를 사용하기 때문에 스택을 적절하게 관리하지 않으면, stack overflow로 이어질 수 있다.

또한 항상 최적의 솔루션을 찾는 것은 아니다. 

 

 

* 트리구조

트리

 

동그란 부분을 노드(node)라고 한다. 

 

 

* 스택 오버플로우(stack overflow)

 

지정한 스택 메모리 사이즈보다 더 많은 스택 메모리를 사용하여 에러가 발생하는 경우.

 

2. 탐색 방법

 

깊이 우선 탐색 방법으로는 전위순회, 중위순회, 후위순회 세 가지가 있다.

이는 부모노드 기준으로 어느 쪽부터 순회하냐에 따라 달라진다. 

 

1) 전위 순회

전위 순회는  부모 - 왼쪽 - 오른쪽 순서대로 순회하는 것을 말한다.

부모가 먼저 순회된다는 뜻이다.

 

전위순회는 1 2 4 5 3 6 7 순서대로 출력된다.

우선, 아래 예시를 통해 어떻게 순회되는지 살펴보자.

 

 

전위순회는 부모먼저 순회하는 것이므로 1번 노드를 먼저 탐색한다.

 

그 후 왼쪽 아래로 내려가면서 탐색한다.

이때에도 2번 노드가 부모이므로 탐색해 준다.

 

 

 

또다시 왼쪽 아래로 내려가서 4번 노드를 탐색해 준다. 

 

4번 노드 아래에 더 이상 노드가 없으므로 다시 부모 노드로 올라간다.

이때 부모 노드는 이미 탐색했으므로 오른쪽 아래로 내려가 5번 노드를 탐색한다.

 

 

 

5번 노드 탐색이 끝난 후, 아래에 더 이상 노드가 없으므로 부모 노드로 올라간다.

2번 노드, 1번 노드 모두 탐색이 끝났기 때문에 3번 노드로 내려온다.

 

6번, 7번 노드로 왼쪽과 마찬가지로 탐색된다.

 

 

*코드구현

 

이제 DFS(깊이우선탐색)를 자바스크립트로 어떻게 구현하는지 알아보자.

깊이우선탐색의 경우 재귀함수와 스택을 사용하기 때문에 미리 익히고 오는 것이 좋다.

(이전 포스팅에 재귀함수, 스택의 개념에 대해서 나와있으니 보고 오는 것을 추천한다!)

 

깊이우선탐색을 구현할 때는 왼쪽 노드는 x*2, 오른쪽 노드는 x*(2+1)로 구현한다는 것을 알아두면 좋다.

 

function solution(n) {
    let answer;

    function DFS(v) {
        //멈추는 곳
        if (v > 7) return
        else {
            //뻗는곳
            console.log(v)
            DFS(v * 2);  //왼쪽
            DFS(v * 2 + 1);  //오른쪽
        }
    }

    DFS(n)
    return answer;
}

console.log(solution(1));

 

앞서 말했듯이 깊이우선탐색을 구현할 때 중요한 것은 중 하나가 종료조건이다.

따라서 무엇을 구현해야 할지 모르겠다면, if else를 통해 종료조건을 먼저 구현해 보자.

 

재귀함수를 호출할 때, 매개변수 값을 계속해서 증가시키면서 이진트리를 만들어 나갈 것이다. 

구현해야 할 이진트리는 총 7까지 있으므로, 값이 7보다 커지는 순간 재귀를 멈춰준다.

 

그 후 왼쪽 노드와 오른쪽 노드를 구현해 주기만 하면 된다.

 

1 2 4 5 3 6 7

 

우선 DFS(1)을 호출하면 해당 함수는 실행 컨텍스트에 저장된다.

그리고 7보다 작으므로 else로 넘어와서 콘솔창에 해당 값인 1을 출력한 후, DFS(v*2)를 호출한다. 

 

DFS(v*2)를 호출하는 순간 DFS(1)은 멈추고, DFS(1*2)가 실행 컨텍스트에 쌓이면서 실행된다.

마찬가지로 7보다 작으므로 else로 넘어와 콘솔창에 해당 값인 2를 출력한 후 DFS(2*2)를 호출한다.

 

 

 

v의 값이  7보다 클 때까지 위 과정이 반복된다.

그리고 DFS(4*2)가 되었을 때, 해당 값이 7보다 커지면서 return 된다.

그럼 가장 위에 있던 DFS(4*2)가 실행 컨텍스트에서 없어지고, 그 아래에 있던 DFS(2*2)가 실행된다.

 

이때 이 전에 실행되지 못했던, DFS(2*2+1)이 실행된다.

해당 값은 7보다 작으므로 콘솔창에 출력되고, DFS(5*2+1)을 호출한다.

 

그 후 DFS(5*2+1)가 return 되면서 실행 컨텍스트에서 나가게 된다.

DFS(2*2+1)도 실행이 끝났으므로 그 아래에 있던 함수가 실행된다.

 

위 과정이 계속해서 반복되면서 콘솔창에 값이 출력된다. 

 

 

2) 중위순회

중위순회는 부모를 중간에 순회하는 방법이다.

왼쪽 - 부모 - 오른쪽 순서대로 탐색한다.

 

중위순회는 4 2 5 1 6 3 7 순서대로 출력된다.

 

 

중위순회는 부모노드에서 자식노드로 이동할 때, 부모노드는 탐색하지 않고 지나간다.

그리고 가장 밑에 있는 자식 노드를 탐색한다.

 

그 후 4번 노드의 부모 노드로 올라와서 2번 노드를 탐색한다.

 

 

 

부모노드를 탐색했으면, 오른쪽으로 다시 내려가서 자식 노드인 5번 노드를 탐색한다.

 

왼쪽 자식노드의 탐색이 끝났으니 부모 노드로 올라와서 1번 노드를 탐색한다.

이를 오른쪽 노드도 반복해 주면 된다.

 

중위순회는 이처럼 왼쪽 자식 노드 > 부모노드 > 오른쪽 자식 노드 순서대로 탐색한다고 생각하면 된다.

 

 

*코드구현

function solution(n) {
    let answer;

    function DFS(v) {
        //멈추는 곳
        if (v > 7) return
        else {
            //뻗는곳
            DFS(v * 2);  //왼쪽
            console.log(v)
            DFS(v * 2 + 1);  //오른쪽
        }
    }

    DFS(n)
    return answer;
}

console.log(solution(1));

 

전위순회와 중위순회, 후위순회는 콘솔을 어디에서 찍냐에 따라 달라진다.

중위순회의 경우 콘솔을 중간에 찍으면 된다. 

 

4 2 5 1 6 3 7

 

DFS(1)이 호출되면, 7보다 작은 값이므로 else로 들어가게 된다.

그리고 DFS(1*2)를 호출한다. 

 

콘솔창은 그 아래에 있기 때문에 아직 실행되지 않았고, 바로 DFS 호출로 넘어간다.

DFS(1*2)도 넘어가고 이 과정이 DFS(4*2)까지 반복된다.

이때까지 콘솔창에는 아무것도 찍히지 않는다.

 

 

그럼 실행 컨텍스트에는 이렇게 호출스택이 쌓여 있을 것이다. 

DFS(4*2)가 if조건에 해당되면서 종료되고, 그 아래에 있는 DFS(2*2)가 실행된다.

이때 console.log(v)가 실행되면서 콘솔창에 4가 출력된다. 

 

그 후 콘솔 아래에 있는 DFS(4*2+1)가 호출되지만, 7이 넘어가므로 바로 리턴된다.

그 아래에 있던 DFS(1*2)가 실행되고, 콘솔창엔 2가 출력된다.

 

DFS(2*2+1)가 실행되면서 5가 출력되고 이 과정이 반복된다.

 

 

 

3) 후위순회

마지막으로 후위순회를 살펴보자.

후위순회는 부모 노드를 가장 마지막에 순회하는 방법이다.

왼쪽 - 오른쪽 - 부모 순서로 탐색한다. 

 

후위순회는 4 5 2 6 7 3 1 순서대로 출력된다.

 

 

후위순회도 이전 순회와 마찬가지로 왼쪽 가장 아래에 있는 자식노드부터 탐색한다.

그 후 부모 노드로 올라온 후 오른쪽에 있는 자식 노드를 탐색한다.

 

이렇게 모든 자식 노드를 탐색한 후 마지막으로 부모노드를 탐색한다.

 

후위순회는 왼쪽 자식 노드 > 오른쪽 자식 노드 > 부모 노드 이렇게 순회한다고 생각하면 된다. 

 

 

*코드구현

 

function solution(v) {
    let answer;

    function DFS(v) {
        //멈추는 곳
        if (v > 7) return
        else {
            //뻗는곳
            DFS(v * 2);  //왼쪽
            DFS(v * 2 + 1);  //오른쪽
            console.log(v)
        }
    }

    DFS(n)
    return answer;
}

console.log(solution(1));

 

후위순회는 콘솔을 마지막에 찍으면 된다. 

 

4 5 2 6 7 3 1

 

마찬가지로 출력 과정을 살펴보자.

 

 

우선, DFS(4*2)까지의 과정은 앞선 순회들과 비슷하다.

 

DFS(4*2)의 실행과정이 끝나면서 DFS(2*2)가 실행되고, 4가 출력된다.

그리고 DFS(1*2)가 실행되면서 DFS(2*2+1)이 호출된다.

 

DFS(2*2+1)은 다시 DFS(5*2)를 호출하지만, 7보다 큰 숫자이므로 리턴된다.

그 후 콘솔에 5가 출력되고, DFS(1*2)가 다시 실행되면서 2가 출력된다.

 

마지막에 있던 DFS(1)이 실행되고, DFS(1*2+1)이 호출된다.

후위순회는 위 과정을 반복하면서 진행된다.