IT 초보 탈출 100일 챌린지

[100일의 IT 초보 탈출] #50 DFS(깊이 우선 탐색) _ 끝까지 파고들어야 보이는 것들

Prof.SSong 2025. 6. 16. 23:08
728x90
반응형

오늘은 무엇을 배우게 될까요?

 

지난 이틀간 우리는 스택(Stack)과 큐(Queue)라는 자료구조를 배웠습니다.

이제부터는 이 자료구조들이 알고리즘에서 실제로 어떻게 활용되는지를 알아보는 시간입니다.

 

오늘은 그래프 탐색 알고리즘 중 하나인 DFS(Depth-First Search)를 통해

문제 해결을 위한 깊이 우선 방식을 배워보겠습니다.

 

 

DFS란?

 

DFS(Depth-First Search)는 말 그대로 깊이 우선 탐색입니다.

 

  • 하나의 정점에서 출발해 가능한 멀리 있는 노드를 먼저 탐색하고 막히면 되돌아가면서 다른 경로를 다시 탐색하는 방식입니다.

 

→ 스택(Stack) 자료구조를 기반으로 작동합니다.

(※ 재귀 함수도 스택처럼 동작합니다.)

 

 

 

DFS 탐색 순서

 

  1. 현재 노드를 방문 처리
  2. 연결된 노드 중 아직 방문하지 않은 노드로 이동
  3. 더 이상 이동할 노드가 없으면 되돌아감(백트래킹)
  4. 모든 노드가 탐색될 때까지 반복

 

 

 

DFS 예시 그래프

A
├── B
│   └── D
└── C
    └── E

DFS 순서: A → B → D → C → E

 

 

 

DFS 실생활 비유

 

  • 미로 탐험:
  • 한 갈래길을 끝까지 가보다가, 막히면 되돌아가서 다른 길 탐색
  • 중첩 폴더 탐색:
  • 한 폴더 안의 폴더 안의 폴더까지 들어갔다가, 더 이상 없으면 위로 나옴

 

 

 

DFS 구현 방법

방법자료구조특징

재귀 방식 함수 호출 스택 간결하지만 깊이가 깊으면 StackOverflow 위험
반복 방식 명시적 스택 재귀보다 안전하지만 구현이 복잡할 수 있음

 

 

 

Python 코드 (재귀 DFS)

# 인접 리스트 방식 그래프
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': [],
    'E': []
}

visited = set()

def dfs(node):
    if node not in visited:
        print(node, end=' ')
        visited.add(node)
        for neighbor in graph[node]:
            dfs(neighbor)

dfs('A')

출력 결과

A B D C E

 

 

 

Python 코드 (반복 DFS - 스택 사용)

def dfs_stack(start_node):
    visited = set()
    stack = [start_node]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            # 연결 노드를 뒤집어서 넣어야 실제 탐색 순서 유지
            stack.extend(reversed(graph[node]))

dfs_stack('A')

 

DFS의 시간 복잡도

 

  • 노드 수: V, 간선 수: E
  • → O(V + E) (그래프 탐색은 대부분 동일)

 

DFS의 활용 사례

분야활용 예시

알고리즘 미로 찾기, 백트래킹 문제, 경로 탐색
보안 순환 참조 탐지, 무한 루프 방지
컴퓨터 이론 위상 정렬, 사이클 검출
게임 퍼즐 게임 탐색, 갈림길 처리 로직

 

 

 

DFS vs BFS 비교

항목 DFS, BFS

탐색 순서 깊이 우선 너비 우선
자료구조 스택 / 재귀 큐
사용 목적 경로 추적, 완전 탐색 최단거리 탐색
구현 난이도 간단(재귀), 위험(Stack Overflow) 메모리 더 필요하지만 안전

※ BFS는 51일차에서 자세히 다룰 예정입니다.

 

 

 

한 줄 요약

 

👉 DFS는 한 갈래를 끝까지 파고드는 방식의 탐색 알고리즘으로,

문제 해결과 백트래킹에 매우 효과적인 도구입니다.

 

728x90
반응형