DFS란?

1. DFS 기본 개념

DFS(Depth-First Search, 깊이 우선 탐색)은 그래프나 트리 같은 자료구조에서 사용되는 탐색 알고리즘 중 하나로, 가장 깊은 노드까지 탐색한 후, 다시 돌아와서 다른 경로를 탐색하는 방식으로 작동합니다. DFS는 트리의 모든 노드를 방문하거나, 그래프의 모든 정점을 탐색할 때 사용됩니다. DFS는 다양한 문제 해결에 적용되며, 알고리즘 자체는 재귀(Recursive)적 구조나 스택(Stack) 자료구조를 통해 구현할 수 있습니다.

백트래킹(Backtracking)의 원리를 응용하는 알고리즘이기에 백트래킹에 대해 먼저 공부하고 오면 이해하기 쉽습니다.
백트래킹에 대한 설명글 링크는 하단에 남기겠습니다.

https://woojin1354.tistory.com/40

백 트래킹(Backtracking)이란?

 

2. 시각적으로 살펴보기

아래 이미지 2개를 살펴보며 DFS 동작을 시각적으로 파악해보겠습니다.

첫번째 이미지는 DFS의 특징을 잘 보여주는 이미지입니다. 한쪽 방향으로 깊게 파고들듯이 탐색하고, 끝 지점(리프 노드)에 도달하면 이전 단계로 거슬러 돌아갑니다.

DFS는 한 방향으로 최대한 깊게 들어가면서 탐색하는 알고리즘입니다. 즉, 어떤 노드에 도달했을 때, 그 노드와 연결된 다음 노드를 즉시 탐색하고, 이를 반복해서 가능한 한 깊이까지 탐색을 진행합니다.

두번째 이미지는 DFS의 동작 과정을 잘 보여주는 이미지입니다. 이미 방문한 노드(visited node)를 체크해가면서 동작한다는 특징 또한 관찰가능합니다.

3. DFS 이해하기

이제 DFS의 동작 과정을 자세히 파악해보겠습니다.

1. 탐색 시작
   DFS는 주어진 시작 노드에서 출발합니다.
2. 탐색 과정
   출발한 노드에서 갈 수 있는 모든 방향 중 하나를 선택해서 끝까지 갑니다. 여기서 '끝'이라는 것은 더 이상 갈 수 있는 이웃 노드가 없는 상태, 즉 "리프 노드(leaf node)"에 도달하는 것입니다. 리프 노드는 더 이상 다른 노드로 이어지지 않는 말단 노드라고 생각할 수 있습니다.
3. 백트래킹
   리프 노드에 도달하면, 더 이상 탐색할 곳이 없기 때문에, 바로 이전 단계(노드)로 되돌아옵니다. 이 과정에서 다음으로 가능한 다른 경로를 탐색합니다.
4. 다른 경로 탐색
   이전 노드로 돌아온 후, 아직 탐색하지 않은 다른 이웃 노드가 있다면 그 노드로 이동하여 다시 깊이 우선으로 탐색을 진행합니다.
5. 과정 반복
   이 과정을 반복하여 그래프나 트리의 모든 노드를 탐색합니다.

4. DFS 구현하기

Python3와 C++로 DFS를 구현해보겠습니다.

그래프 탐색을 위해 DFS를 구현한 간단한 예제입니다. 그래프는 노드와 노드 간의 연결(간선)로 구성된 자료구조로, 여기서는 인접 리스트를 사용하여 그래프를 표현하고 있습니다. DFS는 주어진 시작 노드에서 출발해 가능한 깊이까지 탐색한 후, 더 이상 탐색할 수 없을 때 돌아와서 다른 경로를 탐색하는 방식으로 작동합니다.

노드를 0부터 시작하는 숫자로 표현했습니다. 예를 들어, 0번 노드는 A에 해당하고, 1번 노드는 B에 해당합니다.

현재 노드를 방문 처리하고, 그 노드의 모든 이웃 노드들을 재귀적으로 방문합니다. visited[node]가 False인 경우에만 해당 노드를 방문하고, 방문한 후에는 True로 변경합니다.

DFS 함수

dfs 함수는 특정 노드를 입력받아, 그 노드를 시작으로 DFS를 수행합니다.
방문 확인 및 처리는 if (!visited[node])를 통해 현재 노드가 방문되지 않았음을 확인한 후, "방문 처리"를 합니다.
"방문 처리"는 2가지 작업을 의미하는데,
첫번째는 노드를 출력하는 것 입니다(예시 : cout << node << " ";).
두번째는 해당 노드를 visited 배열에서 true로 표시하는 것입니다(visited[node] = true;).
현재 노드와 연결된 모든 이웃 노드에 대해 재귀적으로 dfs를 호출합니다. 이 과정을 통해 DFS가 노드의 깊이까지 탐색을 진행합니다.

아래는 Python 코드입니다.

def dfs(graph, node, visited):
    # 현재 노드를 방문 처리
    if not visited[node]:
        print(node, end=' ')
        visited[node] = True

        # 이웃 노드를 재귀적으로 방문
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

# 그래프를 인접 리스트로 표현 (노드를 0부터 시작하는 숫자로 표현)
graph = {
    0: [1, 2],  # A -> B, C
    1: [3, 4],  # B -> D, E
    2: [5],     # C -> F
    3: [],      # D
    4: [5],     # E -> F
    5: []       # F
}

visited = [False] * len(graph)  # 모든 노드를 방문하지 않은 상태로 초기화
dfs(graph, 0, visited)  # 0번 노드 (A)부터 DFS 시작

 

아래는 C++ 코드입니다.

#include <iostream>
#include <vector>
using namespace std;

// 전역 변수로 그래프와 방문 배열 선언
vector<vector<int>> graph;
vector<bool> visited;

// DFS 함수
void dfs(int node) {
    // 현재 노드를 방문 처리
    if (!visited[node]) {
        cout << node << " ";
        visited[node] = true;

        // 이웃 노드를 재귀적으로 방문
        for (int neighbor : graph[node]) {
            dfs(neighbor);
        }
    }
}

int main() {
    // 그래프를 인접 리스트로 표현 (0-인덱스 기준)
    graph = {
        {1, 2},    // A (0) -> B (1), C (2)
        {3, 4},    // B (1) -> D (3), E (4)
        {5},       // C (2) -> F (5)
        {},        // D (3)
        {5},       // E (4) -> F (5)
        {}         // F (5)
    };

    visited = vector<bool>(graph.size(), false);  // 모든 노드를 방문하지 않은 상태로 초기화
    dfs(0); // 0번 노드 (A)부터 DFS 시작

    return 0;
}