너비를 기준으로 탐색하는 노드들을 쭉쭉 펼쳐나가는 BFS 와는 다르게, DFS는 자신이 탐색할 수 있는 최종 깊이들을 먼저 탐색해보는 방식이다.

특정 노드에 다른 노드로 연결되는 많은 에지들을 갈림길로 보고 그래프를 하나의 거대한 길이라고 해보자.

이 때 너비우선탐색은 매번 갈림길이 나올 때 마다 나의 분신을 만들어서 모든 갈림길에 퍼트리는 방식인데, 깊이우선탐색은 특정 길 하나를 선택해서 내가 가볼 수 있는 끝까지 가보고, 다시 돌아와서 다른 갈림길로 들어가 끝까지 가보는 방식이다.

즉, 갈림길이 나타날 때 마다 특정 길 하나를 선택한 뒤 내가 가봐야 할 또다른 갈림길이 있다는 정보만 기억해놓고 그 갈림길로 들어간다.

큐를 활용한 BFS와 달리 스택을 활용하여 구현할 수도 있지만, 그보다는 재귀함수를 이용한 방식이 간단하고 직관적이다.

갈림길에 들어설 때 마다 재귀적으로 또다른 갈림길에 들어선 나를 호출하여 경로를 선택한다고 볼 수 있다.

각 지점마다 방문 여부를 관리하지 않을 경우 순환이 이루어지는 구조에서는 무한히 반복되기 때문에 BFS와 마찬가지로 방문 여부에 대한 배열을 관리함으로써 전체 그래프에 대한 탐색을 한번만 수행하게 한다.

DFS를 통해 목적지까지의 경로를 구한다고 하더라도, 이것이 최단경로가 되지는 않는다.

다른 갈림길을 통해 더 빠르게 방문하는 경로가 존재할 수 있지만, 단순히 깊이를 우선으로 들어가다가 방문처리해버리면, 다른 경로에서 들어오지 못하기 때문이다.

따라서 그저 그래프를 탐색하는 방법 중 하나라고 볼 수 있겠다.

1번 노드 입장에서는 갈림길이 2개가 발생하는데, 이 중 2번 노드로 들어가 또다시 갈림길을 선택한다.

2번 노드 입장에서는 1번, 4번, 5번으로의 갈림길이 발생하며, 1번은 이미 방문했기 때문에 4번으로 들어가 다시 갈림길을 선택한다.

4번 노드는 2번과 8번 중 방문하지 않는 노드는 8번 밖에 없기 때문에 그대로 들어가며, 8번 노드 역시 4번과 5번 중 5번을 선택하여 들어간다.

5번 노드 입장에서는 2번과 8번이라는 선택지가 있지만, 둘 다 이미 방문되었기 때문에 아무데도 가지 못하고 종료한다.

종료되면서 이전 갈림길들로 쭉쭉 복귀하는데, 이미 전부 방문되었기 때문에 각 노드마다 남은 선택지가 없어 최종적으로 1번 노드까지 돌아온 뒤, 아까 기억하고 있던 3번 노드로 들어가 다시 탐색을 시작한다.

결국 한 계층마다 퍼져나가는 BFS와는 다르게 1-2-4-8-5-3-6-7 순으로 방문하게 된다.

코드

def dfs(graph, visited, cur):
    # 현재 탐색중인 노드에 대해 방문처리
    visited[cur] = True
    # 현재 노드와 연결된 다른 모든 노드들에 대해서
    for nxt in graph[cur]:
        # 아직 방문하지 않은 노드가 있다면
        if not visited[nxt]:
            # 해당 노드를 기준으로 재귀적으로 호출함으로써 깊이를 우선으로 탐색
            dfs(graph, visited, nxt)

예시

1. DFS를 0번 노드부터 시작한다고 했을 때, 스택을 사용하지 않고 재귀적으로 깊이를 들어가며, 같은 깊이일 경우 작은 노드 순서대로 탐색을 진행한다고 하자.

2. 우선 0번 노드를 방문처리 해준 뒤, 0번 노드와 에지로 연결되어있는 1번과 3번노드 중에 1번 노드를 방문하게 된다.

3. 재귀 호출로 인해 1번 노드를 방문하기 위한 dfs 함수가 호출되고, 1번 노드 입장에서 다시 함수를 수행하게 되기 때문에 자신을 방문처리 해주고 자신과 연결된 다른 노드들을 확인한다.

4. 1번 노드는 0,2,3,5,6번 노드와 연결되어있기 때문에, 가장 크기가 작은 0번 노드를 먼저 방문하려고 시도한다.

5. 그러나 0번 노드는 이전에 이미 방문처리 되었기 때문에 스킵되며, 그다음으로 2번 노드에 대한 dfs 함수를 호출한다.

6. 또다시 2번 노드 입장에서의 dfs 함수를 처리하는 과정에서 2번 노드를 방문처리해주고, 2번 노드와 연결된 1,3,4,5 노드들 중 아직 방문하지 않는 노드를 탐색한다.

7. 그렇게 3번 노드에 대한 dfs가 다시 재귀적으로 호출되고, 그다음으로는 4번, 6번까지 호출되는데, 마지막 6번 노드의 경우에는 1번과 4번이 모두 방문처리 되어있기 때문에 다음 dfs를 호출하지 않고 그대로 종료한다.

8. 지금까지 재귀적으로 호출되었기 때문에, 6번 노드에 대한 dfs 함수가 종료될 경우 4번 노드의 재귀로 돌아오게 되고, 4번 노드 역시 반복문을 다 처리하고 3번 노드로, 2번 노드로 복귀한다.

9. 2번 노드의 경우 연결되어있는 1,3,4,5번 노드들 중에 1,3,4번 노드는 dfs 과정에서 모두 방문처리되었기 때문에, 남은 5번 노드를 호출한다.

10. 5번 노드 역시 방문처리된 이후 더이상 호출할 함수가 없어 종료되어 2번으로 넘어가고, 2번이 종료되면서 1번으로, 다시 0번으로 복귀하면서 그래프상에 연결된 모든 노드들에 대해 깊이 우선 탐색이 완료된다.