[알고리즘] Python3 - DFS/BFS

 

📌 DFS/BFS을 위해 선행되어야 할 개념 

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

최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 경우 옆으로 이동  

 

• 탐색 순서: 깊은 노드부터 탐색 (깊이 우선 탐색)
• 사용 구조: 스택 (Stack) (보통 재귀 함수로 구현)
• 동작 과정:
  1. 시작 노드를 방문하고, 재귀적으로 연결된 노드를 방문합니다.
  2. 더 이상 방문할 노드가 없으면 이전 노드로 되돌아갑니다.
  3. 모든 노드를 방문할 때까지 반복합니다.
• 장점:
  • 메모리 사용량이 적음 (일반적으로 탐색 경로만 저장).
  • 특정 경로 탐색에 적합.
  • BFS에 비해 좀 더 간단함.
• 단점:
  • 최단 경로 보장 X (목적지까지 돌아가는 경로가 최단이 아닐 수 있음).
  • 깊이가 깊은 그래프에서 스택 오버플로우 위험.
  • BFS에 비해 느림.

 

2. 너비 우선 탐색(BFS: Breadth Frist Search):

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동 

• 탐색 순서: 가까운 노드부터 탐색 (넓이 우선 탐색)
• 사용 구조: 큐 (Queue)
• 동작 과정:
  1. 시작 노드를 큐에 넣고 방문 표시를 합니다.
  2. 큐에서 노드를 하나 꺼내어 해당 노드와 연결된 (아직 방문하지 않은) 모든 노드를 큐에 삽입합니다.
  3. 더 이상 큐에 노드가 없을 때까지 반복합니다.
• 장점:
  • 최단 경로 탐색이 필요한 경우 적합 (가중치가 없는 그래프에서 최단 경로 보장).
• 단점:
  • 메모리 사용량이 많을 수 있음 (너비 우선으로 탐색하므로 큐에 많은 노드가 저장될 수 있음).

3. DFS와 BFS의 비교 

 

 

특성	DFS(깊이 우선 탐색)	BFS(너비 우선 탐색)
탐색 순서	깊은 노드부터	가까운 노드부터
구현 구조	스택(재귀/반복)	큐
최단 경로 보장	O	X
메모리 사용	더 적음	더 많음
사용 사례	경로 탐색, 그래프 순회	최단 거리 문제, 레벨 탐색

 

4. 재귀 함수 

DFS와 BFS를 이해하려면 재귀 함수를 이해해야 한다. 

재귀함수란, 자기 자신을 다시 호출하는 함수이다. 

재귀 함수를 구현할 때에는 재귀 함수가 언제 끝날지 종료 조건을 명시하는것이 중요하다. 

종료 조건을 명시하지 않으면 함수가 무한히 호출될 수 있다. 

 

아래는 재귀함수의 대표적인 예시이다. 

def fact_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

def fact_recursive(n):
    if n <= 1:
        return 1
    return n * fact_recursive(n - 1)

print('반복문 구현 : ', fact_iterative(5))
print('재귀 구현 : ', fact_recursive(5))

 

5. Python 예제

 

https://codingopera.tistory.com/67

위와 같은 그래프를 딕셔너리로 표현하면 아래와 같다. 

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와 BFS를 아래와 같이 구현할 수 있다. 

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

    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’]

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

    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']

 

 

참고 사이트:

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

[Algorithm] 깊이우선탐색(DFS)과 너비우선탐색(BFS)