BFS / DFS

DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다. DFS는 깊이 우선 탐색(Depth-First Search)이라고 불리며, BFS는 너비 우선 탐색(Breadth-First Search)이라고 불린다. 이 두 알고리즘은 그래프에서 노드를 탐색하고 경로를 찾는 데 사용된다.

 

 

 

DFS(Depth-First Search)는 그래프에서 깊이 방향으로 탐색하는 알고리즘이다. 시작 노드에서부터 한 방향으로 가능한 한 깊이 탐색을 진행하다가 더 이상 진행할 수 없게 되면, 다시 돌아와서 다른 방향의 노드를 탐색하는 방식이다. 이 알고리즘은 스택, 재귀 호출 등의 방법을 사용하여 구현한다.

 

DFS는 주로 깊이 우선 탐색이 필요한 경우에 사용된다. 예를 들어, 미로 찾기, 트리 탐색, 그래프에서 사이클 찾기 등에서 쓴다. 또한, 경로를 찾는 문제에서 최단 거리를 찾지 않아도 되는 경우에도 DFS를 사용할 수 있다.

 

BFS는 주로 너비 우선 탐색이 필요한 경우에 사용된다. 예를 들어, 최단 경로를 찾는 문제, 미로 탐색에서 최단 거리를 찾는 문제, 그래프에서 최단거리 경로를 찾는 문제 등에서 사용됩니다. BFS는 최단 경로를 찾는 문제에서 유용하게 사용될 수 있다.

 

또한, DFS와 BFS는 각각의 장단점이 있기 때문에, 문제 상황에 따라 적합한 알고리즘을 선택해야 한다. 예를 들어, 그래프의 깊이가 매우 깊은 경우에는 DFS가 더 적합하며, 그래프의 노드 간 거리가 가까운 경우에는 BFS가 더 적합하다.

 

DFS와 BFS 함수를 파이썬으로 구현하면 아래와 같다...!

 

# DFS 함수 구현

def DFS(graph, start_node):
    visited = []
    stack = [start_node]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack.extend(graph[node] - set(visited))

    return visited


# BFS 함수 구현

from collections import deque

def BFS(graph, start_node):
    visited = []
    queue = deque([start_node])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node] - set(visited))

    return visited

 

위 코드에서 graph 는 그래프를 나타내는 리스트이다. start_node 는 탐색을 시작할 노드다. DFS 함수는 스택을 이용하여 구현하였고, BFS 함수는 큐를 이용하여 구현하였다. 각각의 함수는 그래프의 모든 노드를 방문하며, 방문한 노드를 리스트에 저장하여 반환한다.