[파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

DFS란?

 

DFS(Depth First Search)는 그래프의 모든 노드를 탐색하는 방법 중 하나로, 깊이를 우선으로 탐색한 후 더 이상 탐색할 노드가 없다면 이전으로 돌아가 탐색을 이어나가는 탐색 알고리즘입니다. 이 과정에서 재귀 알고리즘을 사용하게 됩니다.

 

그래프 배우기 --> 2022.07.04 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 그래프(Graph)

[파이썬으로 배우는 자료구조] 그래프(Graph)

 

재귀 알고리즘 배우기 --> 2022.07.05 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] 재귀(Recursion) 알고리즘

[파이썬으로 배우는 알고리즘] 재귀(Recursion) 알고리즘

 

탐색 과정

위와 같은 그래프로 1번 노드부터 DFS 알고리즘을 적용하여 탐색을 해보겠습니다. 연결된 노드가 여러개일 때는 오름차순으로 탐색을 하도록 하겠습니다.

 

1) 1번 노드를 방문 처리합니다. 1번 노드와 탐색할 수 있는 노드는 2, 4, 5번 노드입니다.

 

2) 오름차순 탐색이므로 2번 노드를 먼저 탐색합니다. 2번 노드를 방문 처리하고, 2번 노드에서 탐색할 수 있는 노드를 확인합니다. 2번 노드에서 탐색할 수 있는 노드는 6번 노드입니다(1번 노드는 이미 방문).

 

 

3) 6번 노드를 탐색하고, 방문 처리를 합니다. 6번 노드에서는 더 이상 탐색할 수 있는 노드가 없으므로 탐색이 종료됩니다(연결된 2번 노드는 이미 방문). 따라서 2번 노드로 복귀하고, 2번 노드에서도 더 이상 탐색할 수 있는 노드가 없으므로(1, 6번 노드 모두 방문) 1번으로 복귀합니다. 이때 1번 노드에서 탐색할 수 있는 노드는 4, 5번 노드입니다(2번 노드는 이미 방문).

 

4) 오름차순 탐색이므로 4번 노드를 탐색합니다. 이때 4번 노드에서 탐색할 수 있는 노드는 3, 7번 노드입니다(1번 노드는 이미 방문).

 

5) 오름차순 탐색이므로 3번 노드를 탐색합니다. 3번 노드는 더이상 탐색할 수 있는 노드가 없으므로 탐색을 종료하고, 4번 노드로 복귀합니다. 이때 4번 노드에서 탐색할 수 있는 노드는 7번 노드입니다(1, 3번 노드는 이미 방문).

 

 

6) 7번 노드를 탐색합니다. 7번 노드는 더이상 탐색할 수 있는 노드가 없으므로 탐색을 종료하고, 4번 노드로 복귀합니다. 4번 노드도 마찬가지로 더 이상 탐색할 수 있는 노드가 없으므로 탐색을 종료하고, 1번 노드로 복귀합니다. 1번 노드에서 탐색할 수 있는 노드는 5번 노드입니다(2, 4번 노드는 이미 방문).

 

7) 5번 노드를 탐색합니다. 5번 노드에서 탐색할 수 있는 노드는 8번 노드입니다(1번 노드는 이미 방문).

 

8) 8번 노드를 탐색합니다. 8번 노드에서 더이상 탐색할 수 있는 노드가 없으므로 5번 노드로 복귀합니다. 5번 노드도 더이상 탐색할 수 있는 노드가 없으므로 1번 노드로 복귀합니다. 1번 노드는 탐색을 시작한 노드로 연결된 모든 노드에 대해서 탐색을 완료했으므로 종료합니다.

 

---

DFS 알고리즘의 구현 방법

 

위와 같은 플로우를 구현하기 위해서는 재귀 알고리즘을 사용하는데 과연 어떤식으로 사용할까요?

위에서 사용한 그래프를 재귀 알고리즘을 적용해보겠습니다.

DFS(n)는 노드 n에 대해서 DFS 알고리즘을 적용하는 함수라고 가정하고 시작하겠습니다.

1) DFS(1)함수 호출 후, 탐색할 수 있는 노드 찾음. 2, 4, 5번 노드 탐색 가능.

2) DFS(2)함수 호출 후, 탐색할 수 있는 노드 찾음. 6번 노드 탐색 가능.

3) DFS(6)함수 호출 후 탐색할 수 있는 노드 찾음. 탐색할 수 있는 노드 없음. DFS(6) 함수가 종료되고, 호출했던 DFS(2) 함수로 복귀. 마찬가지로 탐색할 수 있는 노드가 없으므로 DFS(2) 함수가 종료되고, 호출했던 DFS(1) 함수로 복귀. 4, 5번 노드 탐색 가능

 

4) DFS(4) 함수 호출 후, 탐색할 수 있는 노드 찾음. 3, 7번 노드 탐색 가능

5) DFS(3) 함수 호출 후, 탐색할 수 있는 노드 찾음. 탐색 할 수 있는 노드 없음. DFS(3) 함수 종료 후 호출했던 DFS(4)로 복귀. 7번 노드 탐색 가능.

 

6) DFS(7) 호출

7) 탐색할 수 있는 노드 없으므로 DFS(7) 함수 종료 후, 호출했던 DFS(4)로 복귀. DFS(4)에서도 탐색할 수 있는 노드 없으므로 DFS(4) 함수 종료 후 DFS(1)로 복귀. 5번 노드 탐색 가능.

8) DFS(5) 호출 후, 탐색할 수 있는 노드 찾음. 8번 노드 탐색 가능.

9) DFS(8) 호출

10) DFS(8)에서 더 이상 탐색 가능한 노드 없으므로 함수 종료 후 DFS(5)로 복귀. DFS(5)에서 더 이상 탐색 가능한 노드 없으므로 함수 종료 후 DFS(1)로 복귀. DFS(1)에서 더 이상 탐색 가능한 노드 없으므로 함수 종료

 

탐색 순서: 1 -> 2 -> 6 -> 4 -> 3 -> 7 -> 5 -> 8

---

DFS 알고리즘의 특징

 

스택 자료구조에 기초 한다는 점에서 구현이 비교적 쉽고, 현 경로상의 노드들만 기억하면 되기 때문에 저장공간 수요가 비교적 적습니다.

 

하지만 스택오버플로우에 유의해야 하며, 해가 없는 경로로 먼저 깊이 우선으로 탐색할 경우 최악의 탐색 성능이 나올 수 있습니다.

 

시간 복잡도

인접행렬 - O(|V|^2) (|V|개의 노드에 대해서 |V|개의 엣지를 모두 탐색해야 함)

인접리스트 - O(|V|+|E|) (|V|개의 노드와 총 |E|개의 엣지 탐색)

---

DFS 알고리즘 구현

코드

# DFS함수
def DFS(graph, v, visited):
    # 방문처리
    visited[v] = True
    print(v, end = ' ')
    # 연결된 노드 중
    for i in graph[v] :
        # 방문 안 한 노드에 대해
        if not visited[i] :
            # 재귀 호출
            DFS(graph, i, visited)

if __name__ == "__main__":
    graph = [
        [],
        # 1번 노드에 연결된 노드들 오름차순으로 연결 표시
        [2, 4, 5],
        [1, 6],
        [4],
        [1, 3, 7],
        [1, 8],
        [2],
        [4],
        [5]
    ]

    # 방문 리스트
    visited = [False] * 9
    # 맨 처음 1번 노드부터
    DFS(graph, 1, visited)

실행 결과