[이코테/Python] DFS / BFS

DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다.

 

여기서 '탐색'은 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 뜻한다.

DFS와 BFS를 구현하기 위해서는 스택, 큐 자료구조와 재귀함수에 대해 숙지해야 한다.

---

 

스택

• 선입후출 (먼저 들어오면 나중에 나감)
• DFS 구현에 사용됨

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack)       # 최하단 원소부터 출력 (들어온 순으로) -> [5, 2, 3, 1]

print(stack[::-1]) # 최상단 원소부터 출력 (최근에 들어온) -> [1, 3, 2, 5]
# or
stack.reverse()
print(stack())     # [1, 3, 2, 5]

 

 

큐

• 선입선출 (먼저 들어오면 먼저 나감)
• BFS 구현에 사용됨

from collections import deque

queue = deque()      # 결과: deque([])
queue2 = deque([1])  # 결과: deque([1])

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue())   # 들어온 순으로 출력 -> deque([3, 7, 1, 4])
queue.reverse()  # 역순
print(queue())   # 나중에 들어온 순으로 -> deque([4, 1, 7, 3])

 

 

재귀함수

• 종료 조건을 반드시 명시해야 함: 명시하지 않으면 무한히 호출되다가 RecursionError 발생
• 함수의 정보가 스택 프레임에 담겨 차례대로 호출되었다가 가장 마지막에 호출된 함수부터 종료됨 → 스택 형태로 실행되기 때문에 DFS 구현에 사용됨
• 모든 재귀 함수는 반복문을 이용해 동일한 기능을 구현할 수 있음 (반대도 성립)

def recursive_function(i):
    if i == 100:
        return
    print(f'{i}번째 재귀 함수에서 {i+1}번째 재귀 함수를 호출합니다.')
    recursive_function(i + 1)
    print(f'{i}번째 재귀 함수를 종료합니다.')

recursive_function(1)

 

---

DFS

• Depth-First Search, 깊이 우선 탐색 → 깊은 부분을 우선적으로 탐색하는 알고리즘

동작 과정

1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리를 한다.
2. 스택의 최상단(가장 최근에 들어온) 노드의 인접한 노드 중에 방문하지 않은 노드가 하나라도 있으면, 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

⇒ 즉, 매번 최상단 원소를 기준으로, 방문하지 않은 인접 노드가 있으면 그 인접한 노드로도 방문 수행

 

DFS 예제

def dfs(graph, v, visited):
    # 현재 노드 방문 처리
    visited[v] = True
    print(v, end=' ')
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
        
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
    [],         # 노드 번호가 1부터 시작하는 경우가 많기 때문에 비워둠
    [2, 3, 8],  # 1번 노드와 인접한 노드 리스트
    [1, 7],     # 2번 노드와 인접한 노드 리스트 
    [1, 4, 5],  # 3번 노드와 인접한 노드 리스트
    [3, 5],     # 4번 노드와 인접한 노드 리스트
    [3, 4],     # 5번 노드와 인접한 노드 리스트
    [7],        # 6번 노드와 인접한 노드 리스트
    [2, 6 ,8],  # 7번 노드와 인접한 노드 리스트
    [1, 7]      # 8번 노드와 인접한 노드 리스트
]
    
visited = [False] * 9   # graph와 같은 크기로 (0~8), 방문은 1부터
dfs(graph, 1, visited)  # 1 2 7 6 8 3 4 5

 

 

BFS

• Breadth-First Search, 너비 우선 탐색 → 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 특정 조건에서의 최단 경로 문제를 해결하기 위한 목적으로 효과적으로 사용됨

동작 과정

1. 탐색 시작 노드를 큐에 삽입하고, 방문 처리를 한다.
2. 큐에서 먼저 들어온 노드 하나를 꺼낸 뒤에, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

DFS vs BFS
DFS: 방문하지 않은 노드를 하나씩 큐에 넣으며 방문 수행
BFS: 방문하지 않은 노드들을 전부 한 번에 큐에 넣음

 

BFS 예제

from collections import deque

def bfs(graph, start, visited):
    # Step 1) 시작 노드를 큐에 삽입하고 방문 처리
    queue = deque([start])
    visited[start] = True
    
    # Step 3) 큐가 빌 때까지 반복
    while queue:
        # Step 2)
        # 먼저 들어온 원소 하나 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        
        # 아직 방문하지 않은 인접 원소들을 큐에 삽입    
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
        
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6 ,8],
    [1, 7]
]
    
visited = [False] * 9
bfs(graph, 1, visited)  # 1 2 3 8 7 4 5 6