[알고리즘] DFS

완전탐색, 백트래킹, DFS, BFS 등에 관련해서 다시 찾아보면서 나름 정리하자면

완전탐색이라는 큰 개념이 있다면 그 구성요소로 백트래킹과 DFS, BFS가 존재한다고 볼 수 있다는 자그만한 이해다.

완전 탐색을 위해서는 백트래킹이 필수이고 BFS가 아닌 탐색은 사실 모두 DFS에 해당한다고 가정 할 수 있을 것 같다.

(예외 상황이 있을 수 있으니)

일반적으로 DFS가 BFS보다 탐색 속도가 느리며, 모든 경우를 탐색할때 주로 많이 쓰인다는 것과,

구현이 비교적 간단하다는 것이 있고, 그래프 탐색에 대해서 또 따로 정리해야 할 것 같다는 생각이 들었다.

또 스택, 큐 개념은 거의 필수적인 요소인 것 같다. 자료들 중에 가끔 스택 큐의 pop을 혼용하는 경우가 많아서 헷갈린다. - -

DFS의 경우 아래 구조에서 크게 벗어난 케이스가 있는가 확인 해보니 없었으니 그냥 지금처럼 해당 구조 기반한 응용만 하면 될 것 같다. 자료를 정리하다보니 머릿속에 해당 로직들이 추상화 되서 선명하게 떠오르기 시작했으니 그것만 해도 나름 가치가 있는듯. 다만 BFS의 경우 아직 구현이 익숙하지 않으니 해당 부분을 따로 정리해야겠다.

function DFS(n, stack = []) {
    if (stack.length > 0) { // 현재 방문중인 노드는 stack에 들어가 있다.
        console.log(stack); // 방문한 노드를 처리하는 로직
    }
    if (n.length > 0) { // n은 방문하지 않은 노드들
    //방문한 노드들을 n에서 제거하니 n은 결국 0이 될때까지 비워진다.
        n.forEach((current, idx) => { 주어진 자료구조의 개별 노드를 탐색한다.
            stack.push(current); // 방문하는 노드
            DFS([...n.slice(0, idx), ...n.slice(idx + 1, n.length)], stack);
            // 해당 노드의 가장 끝 깊이까지 재귀적으로 탐색한다.
            stack.pop(); // 방문이 끝난 노드는 stack에서 제거해준다.
        });
    }
}