Depth First Search(DFS) 완벽 가이드

DFS란?

DFS(깊이 우선 탐색, Depth First Search)는 어떤 문제를 해결하기 위해 깊이 있는 곳까지 먼저 탐색하는 방법입니다.

예를 들어, 미로에서 출구를 찾을 때 한 길을 끝까지 가보고, 막히면 다시 돌아와서 다른 길을 찾는 방식과 같습니다. 즉, 갈 수 있을 때까지 계속 가다가 더 이상 갈 곳이 없으면 뒤로 돌아오는 방식입니다.

DFS는 재귀(함수를 자기 자신을 부르는 방식) 또는 스택(뒤에서 추가하고 꺼내는 자료구조)을 사용하여 구현할 수 있습니다.

Spanning Tree 알고리즘: 네트워크가 루프 없이 원활하게 작동 👆

DFS의 특징

하나의 경로를 끝까지 탐색: 갈 수 있는 길이 있으면 끝까지 간 후에 돌아옵니다.
스택을 활용: 재귀 방식(함수 호출) 또는 직접 스택을 만들어서 구현할 수 있습니다.
백트래킹(되돌아가기): 더 이상 진행할 수 없는 경우 이전 단계로 돌아가 다른 길을 찾습니다.
그래프 탐색 가능: 트리뿐만 아니라 복잡한 네트워크에서도 사용할 수 있습니다.

클라우드 기반 HSM(Cloud-based HSM)이란? 👆

DFS의 동작 원리

탐색을 시작할 노드를 선택합니다. (예: A 노드에서 시작)
해당 노드를 방문하고, 방문했다고 표시합니다.
인접한 노드 중 방문하지 않은 노드를 찾아 재귀적으로 탐색합니다.
더 이상 방문할 노드가 없으면, 이전 노드로 되돌아갑니다.
모든 노드를 탐색할 때까지 위 과정을 반복합니다.

💡 쉽게 생각하면

길이 있으면 계속 갑니다.
막히면 돌아옵니다.
다른 길이 있으면 또 가봅니다.
모든 길을 다 가봤다면 탐색이 끝납니다.

웜(Worm): 스스로 전파되는 악성코드 👆

DFS 구현 방법 (예제 코드 포함)

재귀(Recursive) 방식 (간단한 구현)

# 그래프를 리스트(딕셔너리)로 표현
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C'],
    'G': ['C']
}

visited = set()  # 방문한 노드 저장

def dfs_recursive(node):
    if node not in visited:
        print(node, end=' ')  # 방문한 노드 출력
        visited.add(node)  # 방문 표시
        for neighbor in graph[node]:  # 연결된 노드 탐색
            dfs_recursive(neighbor)

dfs_recursive('A')  # A에서 시작

스택(Stack)을 이용한 반복(Iterative) 방식

# DFS 반복문 구현
def dfs_iterative(start):
    stack = [start]  # 탐색할 노드를 저장할 스택
    visited = set()  # 방문한 노드를 저장할 집합
    
    while stack:
        node = stack.pop()  # 스택에서 노드 꺼내기
        if node not in visited:
            print(node, end=' ')  # 방문한 노드 출력
            visited.add(node)  # 방문 표시
            stack.extend(reversed(graph[node]))  # 방문할 노드 추가

dfs_iterative('A')  # A에서 시작

COCOMO 모델: 소프트웨어 개발 비용 산정 👆

DFS의 시간 복잡도

DFS의 시간 복잡도는 O(V + E)입니다.

V: 노드(Vertex, 즉 점)의 개수
E: 간선(Edge, 즉 선)의 개수

노드와 연결된 선을 한 번씩 방문하기 때문에 V(점) + E(선) 만큼의 시간이 걸립니다.

SHA(Secure Hash Algorithm) – 안전한 해시 알고리즘 👆

DFS의 활용 사례

DFS는 여러 가지 문제를 해결하는 데 사용할 수 있습니다.

✅ 미로 탐색: 출구까지의 경로 찾기

✅ 그래프 연결 요소 찾기: 연결된 그룹 찾기

✅ 위상 정렬: 방향 그래프에서의 순서 정하기

✅ 퍼즐 해결: N-Queen 문제, 미로 문제 등

💡 쉽게 말하면: DFS는 길을 찾는 문제나 순서를 정하는 문제에서 유용합니다!

SYN Flooding 공격이란? 👆

BFS와 DFS 비교

DFS와 비슷한 개념으로 BFS(너비 우선 탐색)가 있습니다.

특징	DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
탐색 방식	한 길을 끝까지 탐색 후 돌아감	가까운 곳부터 탐색
자료구조	스택 (재귀 또는 직접 구현)	큐 (Queue) 사용
최단 경로 보장	❌ (돌아가는 경우가 많음)	✅ (최단 거리 보장)
사용 예시	미로 찾기, 퍼즐 해결	최단 거리 찾기