[자료구조 및 알고리즘] DFS (Depth First Search, 깊이우선탐색)

해당 글은 https://8iggy.tistory.com/104 를 참고하여 썼습니다.

 

DFS

 

진짜 어렵다... 너무 어렵다. 그래도 해야겠지. 가봅시다. DFS는 그래프 탐색을 할 때 사용하는 알고리즘으로, Depth First Search의 줄임말이다. 깊이 우선 탐색을 뜻하며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 stack이나 재귀함수를 이용해서 구현할 수 있다. 

 

DFS의 동작과정은 다음과 같다.

 

1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.

 

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 노드가 없다면 스택에서 최상단 노드를 꺼낸다.

 

3. 2의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

주의사항

 

노드의 방문여부를 체크하지 않아 무한루프에 빠지거나 stack 상태를 체크하지 않아 스택 오버플로가 발생하게끔 하지 않아야 할 것이다.

 

DFS 특징

 

1. 모든 조건을 만족하는 모든 경우의 수에 대해 탐색을 진행

2. 자기 자신을 호출하는 순환 알고리즘의 형태를 갖는다. (재귀형태)

3. BFS보다 탐색 속도가 느리다.

4. 백 트래킹에 사용되는 알고리즘이다.

 

DFS 장점

 

1. 저장공간이 적게 요구된다.

2. 찾고자 하는 값이 깊은 곳에 있다면 빠르게 찾을 수 있다.

3. 구현이 상대적으로 쉬운 편이다.

 

DFS 단점

 

1. DFS는 해를 찾으면 탐색을 종료하므로 구한 해가 최단경로임을 보장하지는 않는다고 한다. 따라서 해가 다수일 경우에는 도출된 해가 최적해가 아닐 수 있으므로 해를 저장한 버퍼를 선언한 후 저장된 해들에 대해 추가 탐색을 해야한다.

 

2. 해가 존재하지 않는 경우 계속해서 탐색을 진행할 수 있다. 임의의 종결 조건을 선언하여 종료할 필요가 있다.

 

DFS 코드

 

graph = {1:[2,3,4], 2:[5,6], 3:[8], 4:[8,9], 5:[7], 6:[],7:[3], 8:[], 9:[]}

# 재귀방식

def dfs_recursion(v, path=[]):
    path.append(v)
    for i in graph[v]:
        if i not in path:
            dfs_recursion(i, path)
    return path
print(dfs_recursion(1)) # [1, 2, 5, 7, 3, 8, 6, 4, 9]

# 스택을 이용해 구현

def dfs_recursion(start):
    stack = [start]
    path = []
    while stack:
        v = stack.pop()
        if v not in path:
            path.append(v)
            for i in graph[v]:
                stack.append(i)
    return path
print(dfs_recursion(1)) # [1, 4, 9, 8, 3, 2, 6, 5, 7]