깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) [초등학생도 이해하는 파이썬]

 안녕하세요 '코딩 오페라'블로그를 운영하고 있는 저는 'Master.M'입니다. 저는 현재 '초등학생도 이해하는 파이썬'이라는 주제로 파이썬(python)에 대해 포스팅을 하고 있습니다. 제목처럼 진짜 핵심 내용을 쉽게 설명하는 것을 목표로 하고 있으니 파이썬(python)에 입문하고 싶은 분들은 많은 관심 부탁드립니다. 지금부터 알아볼 내용은 '깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)'입니다. 

 

그래프 탐색 알고리즘에는 '깊이 우선 탐색(DFS)'과 '너비 우선 탐색(BFS)' 이렇게 2가지가 있습니다. 지금부터 이 두 가지 탐색 방법에 대해 알아보도록 하겠습니다. 

 

깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS)

깊이 우선 탐색은 영어로 DFS(Depth Frist Search)으로 깊이를 우선으로 탐색하는 방법입니다. 위 그림과 같이 DFS는 최대한 깊이 내려간 뒤 더 이상 내려갈 곳이 없으면 옆으로 이동하는 방식을 의미합니다. 

 

DFS는 다음과 같은 특징을 가지고 있습니다.

• 모든 노드를 방문하고자 할때 사용되는 방법
• DFS는 BFS(너비 우선 탐색)에 비해 비교적 간단함 
• 검색 속도는 DFS가 BFS에 비해 느림
• 스택이나 재귀함수를 이용하여 구현

 

너비 우선 탐색 (BFS)

너비 우선 탐색 (BFS)

너비 우선 탐색은 영어로 BFS(Breadth Frist Search)으로 너비를 깊이보다 우선적으로 탐색하는 방법입니다. 위 그림과 같이 BFS는 최대한 옆으로 넓게 이동한 뒤 더 이상 옆으로 갈 수 없으면 아래로 이동하는 방식을 의미합니다.

 

BFS는 다음과 같은 특징을 가지고 있습니다.

• 최단 경로를 찾고자 할때 사용 : 위 그림과 같이 BFS는 수평으로 탐색하는 방법이기 때문에 [1-3-7], [1-4-8]과 같은 최단 경로를 중간에 찾을 수 있습니다.
• 예를 들어 A와 B 사이의 관계를 알고 싶을 때 DFS의 경우 모든 경우를 고려해야 될 수도 있지만, BFS는 가까운 관계부터 탐색을 할 수 있습니다. 
• 큐를 이용하여 구현

 

 

지금까지는 DFS와 BFS의 개념에 대해 알아보았습니다. 이제부터는 이 부분의 이해를 돕고자 파이썬 예제를 보여드리겠습니다. 

 

그래프

먼저 위와 같은 그래프가 있을 때, 이를 파이썬 딕셔너리로 표현하면 다음과 같습니다.

 

myGraph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['A', 'H'],
    'E': ['B', 'I'],
    'F': ['C', 'J'],
    'G': ['C'],
    'H': ['D'],
    'I': ['E'],
    'J': ['F']
}

 

"""
DFS(Depth-First Search)
"""

def my_dfs(graph, start_node):
    visited = list() # 방문한 노드를 담을 배열
    stack = list() # 정점과 인접한 방문 예정인 노드를 담을 배열

    stack.append(start_node) # 처음에는 시작 노드 담아주고 시작하기.

    while stack: # 더 이상 방문할 노드가 없을 때까지.
        node = stack.pop() # 방문할 노드를 앞에서 부터 하나싹 꺼내기.

        if node not in visited: # 방문한 노드가 아니라면
            visited.append(node) # visited 배열에 추가
            # stack.extend(graph[node]) # 해당 노드의 자식 노드로 추가
            stack.extend(reversed(graph[node]))

    print("dfs - ", visited)
    return visited
    
# 함수 실행
my_dfs(myGraph, 'A')

dfs -  ['A', 'B', 'E', 'I', 'C', 'F', 'J', 'G', 'D', 'H’]

위와 같이 DFS 파이썬 코드를 돌리면 이와같은 답이 나오는 데, 위에서 배웠던 DFS의 개념을 떠올리면, 그래프의 제일 왼쪽 A-B-E-I부터 C-F-J, G, D-H로 이루어져 있다는 것을 알 수 있습니다. 때문에 DFS 코드가 맞음을 확인할 수 있습니다. 

 

  

"""
BFS(Breath-First Search)
"""

def my_bfs(graph, start_node):
    visited = list() # 방문한 노드를 담을 배열
    queue = list() # 방문 예정인 노드를 담을 배열

    queue.append(start_node) # 처음에는 시작 노드 담아주고 시작하기.

    while queue: # 더 이상 방문할 노드가 없을 때까지.
        node = queue.pop(0) # 방문할 노드를 앞에서 부터 하나싹 꺼내기.

        if node not in visited: # 방문한 노드가 아니라면
            visited.append(node) # visited 배열에 추가
            queue.extend(graph[node]) # 해당 노드의 자식 노드로 추가
    
    print("bfs - ", visited)
    return visited
    
# 함수 실행
my_bfs(myGraph, 'A')

bfs -  ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']

BFS의 경우에도 파이썬 코드를 진행해주면 다음과 같은 결과가 나오는데, 이 역시 가로방향 알파벳 순으로 만든 그래프와 동일하게 도출되는 것을 확인할 수 있습니다. 

 

 

  지금 까지 저희는 '깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)'에 대해 알아보았습니다. 도움이 되셨나요? 만약 되셨다면 구독 및 좋아요로 표현해 주시면 정말 많은 힘이 됩니다. 궁금한 사항 혹은 앞으로 다루어 주었으면 좋을 주제가 있으시면 댓글 남겨주시면 감사하겠습니다. 저는 '코딩 오페라'의 'Master.M'이었습니다. 감사합니다.