DFS(Depth First Searching)

그래프 탐색 알고리즘 중 하나로, 한 노드에서 출발하여 최대한 깊이 내려간 뒤, 더 이상 갈 곳이 없으면 되돌아오면서 다른 경로를 탐색하는 방식이다.

---

특징

• 스택 또는 재귀 를 사용
  -> 일반적으로 재귀 함수로 구현하지만, 스택을 활용한 반복문으로도 구현 가능하다.
• 백트래킹 과 자주 사용
  -> 모든 경우의 수를 탐색할 때, 필요 없는 경로는 가지 않고 되돌아오는 방식
• 그래프 탐색에서 DFS vs BFS
  -> DFS: 경로 탐색에 유리(미로 찾기, 백트래킹 문제)
  -> BFS: 최단 거리 탐색에 유리(길 찾기, 네트워크 문제)

---

예시 그래프
    1
   /|\
  2 3 4
 /| |
5 6 7

---

재귀 함수를 이용한 DFS 예제

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

    for neighbor in graph[node]:  # 현재 노드의 인접 노드 탐색
        if not visited[neighbor]:  # 방문하지 않은 경우 DFS 호출
            dfs(graph, neighbor, visited)

# 예제 그래프 (인접 리스트 표현)  
# 각 노드가 어디와 연결되어있는지 표시 ex) 1은 2,3,4와 연결 
graph = {
    1: [2, 3, 4],
    2: [1, 5, 6],
    3: [1, 7],
    4: [1],
    5: [2],
    6: [2],
    7: [3]
}

# 방문 여부 리스트 (노드 번호에 맞게 크기 조정)
visited = {key: False for key in graph}

# DFS 실행 (1번 노드부터 시작)
dfs(graph, 1, visited)

**출력**
1 2 5 6 3 7 4

스택을 활용한 DFS 구현 예제

def dfs_stack(graph, start):
    visited = {key: False for key in graph}  # 방문 여부 초기화
    stack = [start]  # 스택에 시작 노드 추가

    while stack:
        node = stack.pop()  # 스택에서 노드 꺼내기
        if not visited[node]:  
            visited[node] = True
            print(node, end=' ')  # 방문한 노드 출력

            # 인접 노드를 스택에 추가 (역순으로 넣어야 작은 숫자부터 탐색)
            stack.extend(reversed(graph[node]))  
            
graph = {
    1: [2, 3, 4],
    2: [1, 5, 6],
    3: [1, 7],
    4: [1],
    5: [2],
    6: [2],
    7: [3]
}

# DFS 실행 (1번 노드부터 시작)
dfs_stack(graph, 1)


** 출력 **
1 2 5 6 3 7 4

두 방식의 경우

• 재귀 방식은 코드가 간결하지만 스택 오버플로우 위험이 있음
• 스택 방식은 메모리 관리가 효율적이며 더 안전하다.

이해를 위한 일상예제

상황 : 컴퓨터 파일 탐색

C:\Users\내문서
 ├── 보고서
 │    ├── 2023
 │    ├── 2024
 ├── 사진
 │    ├── 여행
 │    ├── 가족
 ├── 동영상

이와 같이 파일 구조가 형성되어 있다면
-> 보고서 폴더에 들어감
-> 2023 폴더 확인 (찾는 파일 없으면 백트래킹)
-> 2024 폴더 확인 (찾는 파일 없으면 백트래킹)
-> 사진 폴더로 이동
-> 여행 -> 가족 -> 동영상
이와 같은 방식으로 이루어진다.