[알고리즘] DFS - 깊이 우선 탐색 개념 정리

깊이 우선 탐색(Depth First Search)은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘이다.

깊이 우선 탐색(Depth First Search)은 맹목적으로 각 노드를 탐색할 때 주로 사용된다.

 

너비 우선 탐색(Breadth First Search)에선 큐가 사용되었다면,

깊이 우선 탐색(DFS)에서는  재귀와 스택(stack)이 사용된다. 

DFS 로직을 구현하는 과정에 재귀 함수를 활용하기 때문에,

더 이상 child node가 존재하지 않을 때까지 콜스택의 상단에 계속 쌓이게 되고,

끝에 다다랐을 경우부터 하나씩 pop up되면서 값이 담기기 때문이다.

컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문에 스택을 사용하지 않아도 구현이 가능하다는 특징이 있다. 

 

DFS의 특징은

자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.

이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우

어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것이다.

검사를 하지 않을 경우엔 무한루프에 빠질 위험이 있다.

 

DFS의 장점은 메모리를 덜 잡아먹고, 또한 자식노드가 존재하는지에 대한 물음을 기반으로 탐색하기 때문에, 특정 경로가 존재하는지(Does Path Exist?)를 판단할 때 아주 유용하다.단점은 bfs보다 속도가 느릴 수 있다. 미로 게임 같은 곳에서 경로가 존재하는지를 판별할 때 사용할 수 있다.

 

DFS 예시

정점인 0을 visited 목록에 넣고 모든 정점을 스택에 넣는 것으로 시작한다.

다음으로 스택 맨 위에있는 요소 (1)를 방문하여 인접한 노드로 이동합니다. 

0이 이미 방문되었으므로 대신 2를 방문합니다.

정점 2에는 4에 방문하지 않은 인접 정점이 있으므로 스택 상단에 추가하고 방문합니다

마지막 요소 3을 방문한 후에는 방문하지 않은 인접 노드가 없으므로 그래프의 Depth First Traversal을 완료했습니다.

코드 

let check = []; // 방문점을 체크하기 위한 배열

// 배열안에 배열구조로 인접 정점을 담기
let stack = [[],[],[],[],[],[],[],[]]; // 스택을 이용한건 아니지만 스택처럼 사용하기 위해 stack으로 선언했다.

function dfs (start){
  if(check[start]){ // 모든 정점을 체크하면 리턴
      return;
  }
  check[start] = true; // 방문 표시
  console.log(x); 

  for(let i=0; i<stack[start].length; i++){
    let y = stack[start][i]; // 인접 정점
    dfs(y); // 재귀 구조로 순회
  }
}

// 0과 1연결 
stack[0].push(1);
stack[1].push(0);

// 0과 2연결
stack[0].push(2);
stack[2].push(0);

// 0와 3연결
stack[0].push(3);
stack[3].push(0);

// 1와 2연결
stack[1].push(2);
stack[2].push(1);

// 2와 4연결
stack[2].push(4);
stack[4].push(2);


dfs(0) // 0, 1, 2, 4, 3

 

 

 

출처

https://www.programiz.com/dsa/graph-dfs

https://hidelookit.tistory.com/31

코드출처 :https://ant-programmer.tistory.com/45