DFS와 BFS

---

DFS(Depth-First Search, 깊이 우선 탐색)와 BFS(Breadth-First Search, 너비 우선 탐색)는 그래프 탐색 기법으로, 주어진 그래프에서 특정 노드를 방문하는 방법이다.

---

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

DFS는 한 경로를 끝까지 탐색한 후, 다시 되돌아가 다른 경로를 탐색하는 방식이다. 스택(Stack) 또는 재귀(Recursion)를 사용하여 구현할 수 있다.

동작 방식

1. 시작 노드를 방문하고, 방문한 노드를 스택에 저장하거나 재귀 호출한다.
2. 현재 노드에서 갈 수 있는 노드 중 방문하지 않은 노드를 선택하여 이동한다.
3. 이동한 노드를 방문 처리하고, 다시 2번 과정을 반복한다.
4. 더 이상 방문할 노드가 없으면 이전 노드로 되돌아가 탐색을 계속한다.

시간 복잡도

• 그래프가 V개의 정점과 E개의 간선을 가질 때, DFS의 시간 복잡도는 O(V + E) 이다.

예제 코드 (재귀 방식)

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

    for neighbor in graph[node]:  # 현재 노드와 연결된 모든 인접 노드 확인
        if not visited[neighbor]:  # 방문하지 않은 노드라면 재귀 호출
            dfs(graph, neighbor, visited)

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

visited = {key: False for key in graph}  # 방문 여부 초기화
dfs(graph, 1, visited)  # DFS 탐색 시작

출력 예시

1 2 5 6 3 7 4

---

2. BFS (Breadth-First Search, 너비 우선 탐색)

BFS는 가까운 노드부터 탐색하는 방식이다. 큐(Queue)를 사용하여 구현한다.

동작 방식

1. 시작 노드를 방문하고, 큐에 삽입한다.
2. 큐에서 노드를 꺼내고, 해당 노드의 인접 노드를 모두 확인한다.
3. 방문하지 않은 인접 노드를 방문 처리하고 큐에 삽입한다.
4. 2~3번 과정을 큐가 빌 때까지 반복한다.

시간 복잡도

• DFS와 마찬가지로 O(V + E) 이다.

예제 코드 (큐 활용)

from collections import deque

def bfs(graph, start):
    visited = {key: False for key in graph}  # 방문 여부 초기화
    queue = deque([start])  # 큐 초기화
    visited[start] = True  # 시작 노드 방문 처리

    while queue:  # 큐가 빌 때까지 반복
        node = queue.popleft()  # 큐에서 노드 꺼내기
        print(node, end=' ')  # 방문한 노드 출력

        for neighbor in graph[node]:  # 인접 노드 탐색
            if not visited[neighbor]:  # 방문하지 않은 노드라면
                queue.append(neighbor)  # 큐에 삽입
                visited[neighbor] = True  # 방문 처리

# 그래프 예시 (DFS와 동일한 구조)
bfs(graph, 1)  # BFS 탐색 시작

출력 예시

1 2 3 4 5 6 7

---

3. DFS vs BFS 비교

| | DFS | BFS | |—|—|—| | 탐색 방식 | 깊이 우선 탐색 (한 경로 끝까지) | 너비 우선 탐색 (가까운 노드부터) | | 구현 방법 | 스택(재귀 또는 명시적 스택) | 큐(Queue) | | 메모리 사용 | 재귀 호출 시 스택 메모리 추가 사용 | 큐를 사용하여 더 많은 메모리 필요 | | 특징 | 백트래킹을 활용한 문제에 적합 | 최단 경로 탐색에 적합 | | 적용 예시 | 미로 탐색, 백트래킹, 순열/조합 문제 | 최단 거리 문제 (Dijkstra, A* 등) |

---

4. 언제 DFS, BFS를 사용할까?

• DFS를 사용할 때:
  • 경로를 모두 탐색해야 하는 경우 (예: 미로 탐색, 백트래킹 문제)
  • 순열/조합 탐색 (예: 모든 경우의 수를 구해야 하는 경우)
• BFS를 사용할 때:
  • 최단 경로를 구해야 하는 경우 (예: 최단 거리 문제, 네트워크 탐색)
  • 모든 노드의 거리를 동일하게 탐색해야 하는 경우

예시: 최단 거리 탐색

from collections import deque

def shortest_path_bfs(graph, start, target):
    queue = deque([(start, 0)])  # (노드, 거리) 형태로 큐 초기화
    visited = {key: False for key in graph}
    visited[start] = True

    while queue:
        node, distance = queue.popleft()

        if node == target:  # 목표 노드 도착 시 거리 반환
            return distance

        for neighbor in graph[node]:
            if not visited[neighbor]:
                queue.append((neighbor, distance + 1))
                visited[neighbor] = True

    return -1  # 경로가 없을 경우

# 예제 실행
print(shortest_path_bfs(graph, 1, 7))  # 출력: 2 (1 → 3 → 7)

---

요약

• DFS는 깊이 우선으로 탐색하는 방식으로, 백트래킹 및 경우의 수를 탐색하는 문제에서 유용하다.
• BFS는 너비 우선 탐색을 수행하며, 최단 거리 문제에서 유리하다.
• 시간 복잡도는 둘 다 O(V + E) 이지만, BFS는 큐를 사용하므로 더 많은 메모리를 사용할 수 있다.
• 특정 문제 상황에 따라 DFS와 BFS를 적절히 선택하는 것이 중요하다.