[알고리즘] DFS(Depth First Search)이란?

1. DFS 알고리즘 개념

2. DFS 알고리즘 동작 방식

3. DFS 알고리즘 구현 코드

DFS(Depth First Search) 알고리즘이란?

DFS 알고리즘은 깊이 우선 탐색 알고리즘이다. DFS는 출발 노드에서 최대한 깊이 갈 수 있는 노드까지 가보고, 더 이상 가지 못하지는 경우, 백트래킹(Back Tracking)하여 갈림길에 있는 미방문 노드부터 탐색을 시작하는 방식이다. 일반적으로, 자료구조 재귀(Recursion)와 스택(Stack)을 이용하여 문제를 해결한다. 

동작 방식

DFS는 Pre-order 방식으로 그래프를 순회하는 것이 일반적이지만, 특정 문제에서는 Post-order 방식이 더 편한 경우가 있기 때문에 알아두는 것이 좋다. DFS 개념을 간단히 이해하고 싶다면 Post-order 방식은 스킵하여도 된다.

 

아래의 무방향 그래프 예시로 동작 방식을 자세히 살펴보자. 같은 레벨인 경우, 작은 번호 기준으로 방문한다고 가정한다.

 

Pre-order Traversal (전위 순회)

Pre-order Traversal은 노드를 방문하고 나서, 그 노드의 자식 노드들을 순차적으로 방문하는 방식이다.

순회 순서: 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리

• 시작 노드 1번을 스택에 넣고 방문 처리한다. 
• 스택의 top에 있는 노드 1번과 인접한 노드 2번을 스택에 넣고 방문 처리한다. 
• 다시 스택의 top에 있는 노드 2번과 인접한 노드 6번을 스택에 넣고 방문 처리한다. 
• 위와 같은 방식으로, 노드 6번의 인접한 노드인 7번을 스택에 넣고 방문처리한다. 
• 노드 7번과 인접한 방문하지 않은 노드가 없기 때문에 노드 7번을 스택에서 꺼내고, 노드 6번으로 백트래킹한다. 
• 노드 6번에서도 방문하지 않은 인접 노드가 없으므로, 노드 6번을 스택에서 꺼내고, 다시 노드 2번으로 백트래킹한다. 
• 노드 2번에서 인접한 노드 중 아직 방문하지 않은 8번 노드를 스택에 넣고 방문처리한다. 
• ...
• 마지막으로, 스택에서 1을 꺼낸다. 

 

Post-order Traversal (후위 순회)

Post-order Traversal은 노드의 자식 노드들을 모두 방문한 후에 현재 노드를 방문하는 방식이다.

순회 순서: 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트

• 시작 노드 1번과 인접한 노드인 2번 노드를 스택에 넣는다. 
• 스택의 top에 있는 노드 2번과 인접한 노드인 6번을 다시 스택에 넣는다. 
• 다시 스택의 top에 있는 노드 6번과 인접한 노드 7번을 스택에 넣는다.
• 노드 7번과 인접한 방문하지 않은 노드가 존재하지 않으므로, 노드 7번을 방문 처리하고 스택에서 꺼낸다.
• 노드 6번으로 백트래킹하고, 6번 노드와 인접한 노드가 더 이상 없기 때문에 6번 노드를 방문처리하고 스택에서 꺼낸다.
• 노드 2번으로 백트래킹하고, 인접한 노드 8번을 아직 방문하지 않았기 때문에 노드 8번을 스택에 넣는다.
• ...
• 마지막으로, 스택에 남아 있는 시작 노드 1번을 방문 처리하고 스택에서 꺼낸다. 

C++ DFS 구현 코드

Recursion 버전

#include<bits/stdc++.h>

using namespace std;

bool visited[9]; // 방문 여부를 기록하는 배열
vector<int> graph[9]; // 그래프를 인접 리스트로 표현

void dfs(int x) {
    visited[x] = true; // 현재 노드 방문 처리
    cout << x << ' '; // 방문한 노드 출력

    for (int i = 0; i < graph[x].size(); i++) {
        int y = graph[x][i];
        if (!visited[y]) {
            dfs(y); // 방문하지 않은 노드에 대해 재귀적으로 DFS 호출
        }
    }
}

int main(void) {
    // 그래프 초기화 (노드 간의 간선 연결)
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[2].push_back(4);
    graph[2].push_back(5);
    graph[3].push_back(6);
    graph[3].push_back(7);
    graph[4].push_back(8);
    graph[5].push_back(9);

    // DFS 수행
    dfs(1);

    return 0;
}

 

Stack 버전

#include<bits/stdc++.h>

using namespace std;

bool visited[9]; // 방문 여부를 기록하는 배열
vector<int> graph[9]; // 그래프를 인접 리스트로 표현

void dfs(int start) {
    stack<int> s; // DFS를 위한 스택
    s.push(start); // 시작 노드를 스택에 넣음
    visited[start] = true; // 시작 노드 방문 처리

    while (!s.empty()) {
        int x = s.top(); // 스택의 최상단 노드를 가져옴
        s.pop();
        cout << x << ' '; // 방문한 노드를 출력

        // 현재 노드와 연결된 노드들에 대해 탐색
        for (int i = graph[x].size() - 1; i >= 0; i--) {
            int y = graph[x][i];
            if (!visited[y]) {
                s.push(y); // 스택에 인접 노드 추가
                visited[y] = true; // 방문 처리
            }
        }
    }
}

int main(void) {
    // 그래프 초기화 (노드 간의 간선 연결)
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[2].push_back(4);
    graph[2].push_back(5);
    graph[3].push_back(6);
    graph[3].push_back(7);
    graph[4].push_back(8);
    graph[5].push_back(9);

    // DFS 수행
    dfs(1);

    return 0;
}

 

출력 결과는 다음과 같습니다.

 

References

(이코테 2021 강의 몰아보기) 3. DFS & BFS