[DFS] 알고리즘 - 깊이 우선 탐색 (DFS)

깊이 우선 탐색 알고리즘 (DFS)

한 루트로 들어가 가장 깊이 들어가서 탐색후 돌아가 다시 다른 루트로 가장 깊이 탐색하는 방식이다.

• 넓게 탐색하는 것이 아닌 깊이 탐색하는 방식이다.
• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
• 스택 자료구조를 사용한다.

 

구현 방법

• 재귀 호출
• 스택 배열

 

동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
3. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다.

 

사용 용도 

• 순회를 하는 경우에 많이 사용된다.
• 백트레킹에 사용된다.
• 자동 미로 생성에 많이 사용된다.
• 유향 그래프에서 사이클 존재 유무를 판단하는 것도 가능하다.

 

장점 : 저장 공간의 수요가 적다. 목표 노드가 깊은 단계에 있을 경우 빨리 해를 구할 수 있다.
단점 : 해가 없는 경로에 깊이 빠질 수 있다. -> 미리 지정한임의 깊이 까지 탐색하고 목표노드가 없을시 다음 경로를 따라 탐색하는 방법이 유용할 수 있다.
          얻어지는 해가 최단경로가 된다는 보장이 없다. -> 경로가 다수인 문제에 대해 깊이 우선 탐색은 해에 다다르면 탐색을 끝내버리므로 이때 얻어지는 해는 최적이 아닐 수 있다.
          BFS보다 검색 속도가 느리다.

 

DFS 특징

• 자기 자신을 호출하는 재귀 알고리즘 형태를 가지고 있다. 
• 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.

 

시간 복잡도 (N : 정점의 수 , E : 간선의 수)

• 인접 리스트로 표현된 그래프 : O(N+E)
• 인접 행렬로 표현된 그래프 : O(N^2)

====> 그래프 내의 적은 숫자의 간선을 가지는 희소 그래프의 경우 인접 행렬보다 인접 리스트 사용이 유리하다.

 

 

구현 방법

DFS는 스택을 활용한 알고리즘이기 때문에 재귀 함수를 이용했을 때 매우 간결하게 구현이 가능하다.

 

1. list 활용

def DFS(graph, root):
    n_visited, visted = [], []
    n_visited.append(root)
    
    while n_visited:
    	n = n_visted.pop()
        
        if n not in visited:
        	visited.append(n)
            n_visited.extend(graph[n])
            
    return visited

2. deque 활용

from collections import deque
def DFS(graph, root):
	visited = []
    q = deque()
    q.append(root)
    
    while q:
    	n = q.pop()
        if n not in visited:
        	visited.append(n)
            q.extend(graph(n))
            
     return visited

3. 재귀함수 활용

def DFS(graph, root, visited):
	visited.append(start)
    
    for n in graph[root]:
    	if n not in visited:
        	DFS(graph, root, visited)
    
    return visited