[그래프 탐색] 깊이 우선 탐색(Depth First Search, DFS)

 

 

깊이 우선 탐색(Depth-First Search, DFS)

깊이 우선 탐색(DFS)은 그래프 탐색 알고리즘 중 하나로, 한 정점에서 시작하여 가능한 깊이까지 탐색한 후, 더 이상 갈 곳이 없으면 되돌아오는 방식(백트래킹)으로 동작합니다.

---

🔹 DFS 개념

DFS는 스택(재귀 호출 or 명시적 스택)을 사용하여 그래프를 깊게 탐색하는 방법입니다.

• 먼저 현재 노드를 방문하고,
• 방문하지 않은 인접 노드가 있으면 해당 노드로 이동하여 탐색을 계속함.
• 더 이상 방문할 노드가 없으면 이전 노드(부모 노드)로 돌아감(백트래킹).

---

🔹 DFS 동작 방식

DFS의 기본 동작 순서는 다음과 같습니다.

1. 시작 노드를 방문하고 방문 처리
2. 현재 노드에서 갈 수 있는 노드를 확인
   • 방문하지 않은 노드가 있으면 해당 노드로 이동
   • 방문한 노드라면 스킵
3. 더 이상 방문할 노드가 없으면 이전 노드로 되돌아감
4. 모든 노드를 방문할 때까지 2~3 과정 반복

---

🔹 DFS 구현 방법

DFS는 두 가지 방식으로 구현할 수 있습니다.

1. 재귀(Recursive) 방식
2. 스택(Stack) 사용 방식(반복문)

---

🟢 1. DFS 재귀(Recursive) 방식 구현 (Python)

def dfs_recursive(graph, node, visited):
    if node in visited:  # 이미 방문한 경우 종료
        return
    visited.add(node)  # 방문 처리
    print(node, end=" ")  # 방문한 노드 출력

    for neighbor in graph[node]:  # 인접 노드 탐색
        dfs_recursive(graph, neighbor, visited)

# 그래프 (인접 리스트 방식)
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6, 7],
    4: [],
    5: [],
    6: [],
    7: []
}

visited_set = set()
dfs_recursive(graph, 1, visited_set)

출력:

1 2 4 5 3 6 7

📌 재귀 방식은 스택을 이용한 것과 동일한 원리로 동작합니다.

---

 

🟢 2. DFS 스택(Stack) 사용 방식 구현 (반복문)

def dfs_stack(graph, start):
    visited = set()
    stack = [start]  # 스택 초기화

    while stack:
        node = stack.pop()  # 스택에서 노드 꺼내기
        if node not in visited:
            visited.add(node)  # 방문 처리
            print(node, end=" ")  

            # 스택에 인접 노드를 추가 (반대로 넣으면 순서 유지)
            stack.extend(reversed(graph[node]))

# 그래프 (인접 리스트 방식)
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6, 7],
    4: [],
    5: [],
    6: [],
    7: []
}

dfs_stack(graph, 1)

출력:

1 2 4 5 3 6 7

📌 스택을 사용하면 재귀 없이 DFS를 구현할 수 있습니다.

---

 

🔹 DFS vs BFS 차이점

비교 항목	DFS(Depth-First Search)	BFS(Breadth-First Search)
탐색 방식	최대한 깊이 탐색 후 백트래킹	현재 레벨(너비)에서 탐색 후 다음 레벨로 이동
자료구조	스택 (or 재귀 호출)	큐 (Queue)
경로 탐색	모든 경로를 탐색해야 하는 경우 적합	최단 경로(가중치 없는 그래프) 탐색에 적합
구현 난이도	비교적 간단	상대적으로 복잡
사용 예시	백트래킹(미로 찾기, 퍼즐 해결, 조합)	최단 경로 탐색 (길 찾기, 네트워크 탐색)

---

🔹 DFS 응용 사례

1. 그래프 탐색
   • 연결 요소 찾기, 경로 탐색
2. 백트래킹 문제 해결
   • 퍼즐 문제 (예: N-Queen 문제)
   • 조합(combination)과 순열(permutation)
3. 네트워크 연결 여부 확인
   • 네트워크 그래프에서 연결 여부 검사
4. 사이클 검출
   • 방향/무방향 그래프에서 사이클 존재 여부 확인
5. 미로 찾기 (DFS 기반 백트래킹)
   • 한 경로를 끝까지 탐색한 후 다른 경로 탐색
     
     

---

🔹 DFS 시간 복잡도 & 공간 복잡도

• 시간 복잡도:
  • 인접 리스트: O(V + E) (정점 V, 간선 E)
  • 인접 행렬: O(V²)
• 공간 복잡도:
  • O(V) (방문 처리 배열, 스택/재귀 호출 스택)

---

🔹 코딩 테스트 문제(백준 2023)

1. 문제 설명

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.(https://www.acmicpc.net/problem/2023)

(제한 시간 2초, 1<= N <= 8)

2. 처음에 사용한 방법(C++ 17)

처음에는 DFS문제라는 것을 깨닫지 못하고, std::string을 활용해서 문제를 풀었습니다. 초기 버전은 제한시간을 훌쩍 넘겼으나, 2의 배수는 소수가 될 수 없다(2 제외) 라는 규칙을 깨닫고 짝수를 제외하자 1850ms 로 겨우 통과했습니다. 하지만 N이 조금이라도 늘었을 경우에는 복사연산과 더불어 시간이 많이 소요되는 좋지 않은 코드였습니다. 우선 먼저 코드를 보여드리겠습니다.

// 백준 2023
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

bool isPrime(int num) {
    if (num <= 1) return false; // 1 이하의 숫자는 소수가 아님
    if (num <= 3) return true;  // 2와 3은 소수
    if (num % 2 == 0 || num % 3 == 0) return false; // 2와 3으로 나누어 떨어지면 소수가 아님

    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
    }
    return true;
}

int main()
{
    int N;
    cin >> N;

    int min = pow(10, N-1);
    int max = pow(10, N);
    for (int i = min; i < max; i++)
    {
        if (i > 10 && i % 2 == 0)
            continue;

        bool isPrimeNumber = true;
        string str = to_string(i);
        for (int j = 0; j < str.length(); j++)
        {
            string strNum;
            int idx = 0;
            while (idx <= j)
                strNum += str[idx++];

            int target = stoi(strNum);
            if (!isPrime(target))
            {
                isPrimeNumber = false;
                break;
            }
        }

        if (isPrimeNumber)
            cout << i << endl;
    }
}

 

3. DFS를 활용한 최종 방법(C++ 17)

허무하게도 DFS는 0ms가 걸렸습니다. 일의 자리에서 소수는 2, 3, 5, 7 뿐이고 그 이후에 올 수 있는 수는 5개(홀수) 뿐입니다. 2 -> 23, 23-> 233 -> 2337 처럼 깊이 우선 방식으로 서치해나가는 DFS를 활용하면 쉽게 풀 수 있다는 것을 알 수 있습니다. 문제를 보고 DFS를 활용해야겠다고 생각하는 것이 가장 중요하다고 볼 수 있습니다.

// 백준 2023
#include <iostream>
#include <vector>
using namespace std;
int N;

bool isPrime(int num) {
    if (num <= 1) return false; // 1 이하의 숫자는 소수가 아님
    if (num <= 3) return true;  // 2와 3은 소수
    if (num % 2 == 0 || num % 3 == 0) return false; // 2와 3으로 나누어 떨어지면 소수가 아님

    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
    }
    return true;
}

void DFS(int num, int digit)
{
    if (digit == N)
    {
        if (isPrime(num))
        {
            cout << num << endl;
            return;
        }
    }

    for (int i = 1; i < 10; i += 2)
    {
        int next = num * 10 + i;
        if (isPrime(next))
            DFS(next, digit + 1);
    }
}

int main()
{
    cin >> N;
    DFS(2, 1);
    DFS(3, 1);
    DFS(5, 1);
    DFS(7, 1);
}

 

🔹 정리

• DFS는 스택(LIFO) 구조를 활용하여 그래프를 깊이 탐색하는 알고리즘
• 재귀(Recursive) 방식과 스택(Stack) 방식으로 구현 가능
• 백트래킹, 미로 탐색, 경로 탐색 등 다양한 문제 해결에 사용
• BFS와 비교하면 최단 경로 탐색보다는 모든 경우의 수를 탐색할 때 유리함

DFS가 필요한 상황이라면, 재귀 방식과 스택 방식 중 적절한 방법을 선택해서 사용하면 됩니다. 🚀