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

그래프 탐색

• 하나의 정점으로부터 시작하여 차례대로 모든 정점들은 한 번씩 방문하는 것
• ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 확인

 

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

 

깊이 우선 탐색은 루트 노트(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

 

• 미로를 탐색할 때, 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아온 후에 다른 방향으로 탐색을 진행하는 방법과 유사하다.
• 넓게 탐색하기 전에 깊게 탐색하는 방식이다.
• 모든 노드를 방문하고자 하는 경우에 이 방법을 사용한다.
• 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다.
• 단순 검색 속도 자체는 너비 우선 탐색에 비해서 느리다.

 

깊이 우선 탐색(DFS)의 특징

•  자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
• 전위 순회(Pre-Order Traversals, 뿌리 - 왼쪽 자식 - 오른쪽 자식 순)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류다.
• 그래프 탐색의 경우 어떤 노드를 방문했는지의 여부를 반드시 검사해야한다. 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.

 

깊이 우선 탐색(DFS)의 과정

 

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

 

 

다음은 깊이 우선 탐색의 과정을 그림으로 나타낸 것이다. 초록색은 최상단 노드, 파란색은 방문 처리된 노드를 표현한다.

 

깊이 우선 탐색 1번째

 

 

시작 노드인 '1'을 스택에 삽입하고 방문 처리 및 최상단 노드 처리를 한다.

 

깊이 우선 탐색 2번째

 

 

최상단 노드 '1'의 인접 노드인 '3'을 스택에 넣고 방문 처리 및 최상단 노드 처리를 한다.

 

깊이 우선 탐색 3번째

 

 

최상단 노드 '3'의 인접 노드 '4'와 '5' 중에 가장 작은 노드 '4'를 스택에 넣고 방문 처리를 한다.

 

깊이 우선 탐색 4번째

 

 

최상단 노드인 '4'에 방문하지 않은 인접 노드가 존재하지 않기 때문에 스택에서 '4'를 제거한다.

최상단 노드는 '3'이 된다.

 

깊이 우선 탐색 5번째

 

 

스택의 최상단 노드인 '3'에 방문하지 않은 인접 노드 '5'를 스택에 넣고 방문 처리를 한다.

 

깊이 우선 탐색 6번째

 

 

최상단 노드인 '5'의 인접 노드 '2'를 스택에 넣고 방문 처리를 한다.

 

깊이 우선 탐색 7번째

 

 

최상단 노드인 '2'에 방문하지 않은 인접 노드가 존재하지 않기 때문에 스택에서 '2'를 제거한다.

 

깊이 우선 탐색 8번째

 

 

깊이 우선 탐색 7번째의 과정을 반복하면 스택은 비워지고 모든 노드를 방문한 것이 된다.

결과적으로 노드의 방문 순서는 1 - 3 - 4 - 5 - 2가 된다.

 

 

깊이 우선 탐색(DFS)의 시간 복잡도

 

• DFS는 그래프(정점의 수: N, 간선의 수: E)의 모든 간선을 조회한다.
  • 인접 리스트로 표현된 그래프: O(N+E)
  • 인접 행렬로 표현된 그래프: O(N^2)
• 즉, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

 

DFS in JavaScript

 

 

const graph = {			// 각 노드 별 인접 노드
    A: ["B", "C"],
    B: ["A", "D"],
    C: ["A", "G", "H", "I"],
    D: ["B", "E", "F"],
    E: ["D"],
    F: ["D"],
    G: ["C"],
    H: ["C"],    
    I: ["C", "J"],
    J: ["I"],
};

const DFS = (graph, startNode) => {
	const visited = [];		// 탐색을 마친 노드들
    let needVisit = [];		// 탐색해야 할 노드들
    
    needVisit.push(startNode);	// 노드 탐색 시작
    
    while (needVisit.length !== 0) {	// 탐색해야 할 노드가 남았다면
        const node = needVisit.shift();	// queue이기 때문에 선입선출, shift() 사용
        if (!visited.includes(node)) {	// 해당 노드가 탐색된 적 없다면
        	visited.push(node);		// 방문 목록에 노드 추가
            needVisit = [...graph[node], ...needvisit];
        }
    }
    return visited;
};

// ["A", "B", "D", "E", "F", "C", "G", "H", "I", "J"]

 

 

 

참고자료

 

 

[자료구조] 트리(Tree)의 개념 및 전위순회, 중위순회, 후위순회, 층별순회

[JS] BFS, DFS

[Algorithm] 깊이 우선 탐색(DFS)은 뭐야?