코딩테스트

DFS(Depth-First Search) vs BFS(Breadth-First Search)

꼬꼬마코더 2024. 5. 20. 14:41
728x90

DFS (Depth-First Search)와 BFS (Breadth-First Search)는 그래프 또는 트리 탐색 알고리즘입니다. 두 알고리즘은 구조적 탐색을 수행하지만 서로 다른 방식으로 그래프나 트리의 노드를 탐색합니다.

DFS (Depth-First Search)

DFS는 가능한 깊이까지 탐색을 진행한 후, 더 이상 진행할 수 없으면 다시 돌아와 다른 경로를 탐색하는 방식입니다.

특징:

  • Stack 사용: 일반적으로 재귀(내부적으로 스택 사용) 또는 명시적 스택을 사용하여 구현합니다.
  • 깊이 우선 탐색: 현재 노드의 자식들을 모두 방문한 후, 다른 자식들을 방문합니다.
  • 경로 탐색: 특정 경로가 있는지 확인하거나, 트리의 깊이를 계산할 때 유용합니다.

구현:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # 방문한 노드 출력

    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

# 그래프 예제
graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A', 'F'},
    'D': {'B'},
    'E': {'B', 'F'},
    'F': {'C', 'E'}
}

dfs(graph, 'A')

BFS (Breadth-First Search)

BFS는 현재 노드의 모든 인접 노드를 먼저 탐색한 후, 다음 수준의 노드들을 탐색하는 방식입니다.

특징:

  • Queue 사용: 큐를 사용하여 구현합니다.
  • 너비 우선 탐색: 현재 노드의 모든 인접 노드를 방문한 후, 다음 수준의 노드들을 방문합니다.
  • 최단 경로 탐색: 무향 그래프에서 두 노드 간의 최단 경로를 찾을 때 유용합니다.

구현:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex)  # 방문한 노드 출력

        for next in graph[vertex] - visited:
            visited.add(next)
            queue.append(next)

# 그래프 예제
graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A', 'F'},
    'D': {'B'},
    'E': {'B', 'F'},
    'F': {'C', 'E'}
}

bfs(graph, 'A')

주요 차이점:

  1. 탐색 방법:

    • DFS: 깊이를 우선으로 탐색합니다. 재귀적으로 모든 자식 노드를 방문하고, 더 이상 방문할 곳이 없으면 부모 노드로 돌아옵니다.
    • BFS: 너비를 우선으로 탐색합니다. 현재 노드의 모든 인접 노드를 큐에 추가하고, 큐에서 꺼내며 탐색을 계속합니다.

  2. 구현 방법:

    • DFS: 재귀 또는 명시적 스택을 사용합니다.
    • BFS: 큐를 사용합니다.

  3. 용도:

    • DFS: 특정 경로 찾기, 강한 연결 요소 찾기, 위상 정렬 등.
    • BFS: 최단 경로 찾기, 최단 경로 트리, 레벨 순위 탐색 등.

예시:

  • DFS는 미로를 탈출할 때 모든 경로를 탐색하여 출구를 찾는 데 사용됩니다.
  • BFS는 물이 퍼져 나가는 방식처럼 최단 경로를 찾는 데 사용됩니다.

이러한 차이점들을 이해하고, 문제에 따라 적합한 알고리즘을 선택하는 것이 중요합니다.

댓글수0