DFS (Depth-First Search)

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

깊이 우선 탐색이란?

• 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
  • 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
  • 즉, 넓게 탐색하기 전에 깊에 탐색하는 것이다.
  • When? : 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다!!!!!!!!
  • BFS(너비우선탐색)에 비해서 검색 속도가 느리다.

깊이 우선 탐색 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
• 이 알고리즘을 구현할 때, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다!!!!!!!!

깊이 우선 탐색의 과정

1.  a노드(시작 노드)를 방문한다.
   • 방문한 노드는 방문했다고 표시
2. a와 인접한 노드들을 차례로 순회한다.
   • a와 인접한 노드가 없다면 종료한다.
3.  a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
   • b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.
4. b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.
   • 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
   • 아직 방문이 안 된 정점이 없으면 종료한다.
   • 있으면 다시 그 정점을 시작으로 DFS를 시작한다.

깊이 우선 탐색의 구현

• 구현 방법 2가지
  1. 순환 호출 이용
  2. 명시적인 스택 사용 : 명시적인 스택을 사용하여 방문한 정점들을 스택에 저장하였다가 다시 꺼내어 작업한다. 
• 순환 호출을 이용한 DFS 의사 코드

void search(Node root) {
	if(root == null) return;
    
    //1. root 노드 방문
    visit(root);
    
    root.visited = true; //1-1. 방문한 노드를 표시
    
    //2. root 노드와 인접한 정점을 모두 방문
    
    for each (Node n in root.adjacent) {
    	if(n.visited == false) { //3-1. 인접하면서 (방문X) 정점!
        	search(n); //3. root 노드와 인접한 정점. 정점을 시작으로 DFS를 시작
        }
    }

}

 

 

 

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog