BFS & DFS 알고리즘

도입

브루트 포스 (Brute Force): 완전 탐색 알고리즘이며 가능한 모든 경우의 수에 대해서 탐색을 수행하여 조건이 만족되는 경우를 찾는 방법입니다. (Brute - 무식한 + Force - 힘)

모든 경우를 탐색하기 때문에 100%의 정답률을 보장할 수 있습니다. 그러나 모든 경우를 탐색하기 때문에 실행시간이 매우 오래 걸릴 수 있다는 단점이 존재합니다.

구조에 따라서 브루트 포스는 2가지로 나뉘게 됩니다.

- 선형 구조 (순차 탐색) 
- 비선형 구조 (넓이 우선 탐색 - BFS, 깊이 우선 탐색 - DFS)

순차 탐색은 배열의 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾아내는 알고리즘이며, 탐색 배열이 단방향이기에 선형 탐색 (Linear Search)라고 부르기도 합니다. 

하지만 모든 데이터 탐색이 선형인 구조만 있는게 아닙니다. 비선형의 구조를 탐색할 때는 BFS와 DFS가 존재합니다.

 

BFS (Breadth-First Search) - 너비 우선 탐색

 

BFS는 탐색 트리의 루트노드 (Level 0)에서 목표 노드 (Level 2)까지 단계별로 횡방향으로 탐색을 하는 알고리즘입니다. 횡방향으로 탐색을 수행하기 때문에 Breadth first라는 단어가 붙습니다.

순서는 다음과 같습니다. 

1. Level 0의 임의의 노드에 시작점 (Starter or Initial)을 마크합니다
2. Level 0이 끝나면 Level 1으로 넘어가서 순차적으로 탐색을 수행합니다.
3. 마찬가지로 같은 Level에 속한 노드들을 탐색하면서 끝 Level까지 탐색을 수행합니다. 

*방문이 완료된 또는 탐색이 완료된 지점은 완료가 되었다고 마크를 함으로서 무한 체크에 빠지지 않도록 합니다.

BFS는 큐 (Queue)를 이용하여 방문한 노드들을 차례로 저장한 후 꺼내는 방식으로 구현합니다. 이를 위해서 방문 예정인 대기 큐와 이미 방문한 기록을 남기는 완료 큐 2개로 구현을 하기도 합니다. 방문 대기 큐에서 앞에서부터 하나씩 빼서 이미 방문하였다면 스킵을 수행하고 방문하지 않았다면 방문 리스트에 추가하여 추가된 노드에서 갈 수 있는 노드를 큐 뒤편에 줄을 세우게 됩니다.

 

BFS Example

편의상으로 큐에서 꺼내어서 처리 중인 노드는 빨간색이며, 방문 처리가 완료된 노드는 노란색으로 하겠습니다. 

 

1. 시작 노드인 노드 A를 큐에 삽입하고 방문 처리를 합니다.

 

 

2. 큐에서 노드 A를 꺼내고 노드 A와 인접한 노드 B, C를 큐에 삽입하고 방문 처리 합니다.

 

 

3. 큐에서 B노드를 꺼내고 노드 B와 인접한 D, E 노드를 큐에 삽입하고 방문 처리합니다.

 

 

4. 큐에서 C노드를 꺼내고 노드 C와 인접한 F노드를 큐에 삽입하고 방문 처리 합니다.

 

5. 그래프에 방문하지 않은 노드가 없으므로 큐에서 모든 노드를 차례대로 꺼내어서 마무리 합니다. 

 

최종적으로 큐에서 삽입한 순서 (노드의 탐색 순서)는 아래와 같습니다.

A → B → C → D → E → F

 

BFS Example Code

위의 예시를 코드로 구현해보겠습니다. BFS 알고리즘의 설명을 위해서 큐를 사용했으며 파이썬 내부에 deque 라이브러리를 사용하여서 구현을 할 수 있습니다. 

# 먼저 collections 모듈에서 deque 라이브러리 불러오기
from collections import deque

# BFS 함수 제작하기
def bfs (graph, node, visited):
    # deque 라이브러리 활용
    queue = deque([node])
    
    # 현재 노드 방문 처리
    visited[node] = True
    
    # 큐에 아무것도 남지 않도록 반복 수행
    while queue:
        # 큐에 삽입된 순서대로 노드 꺼내기
        checked = queue.popleft()
        
        # 탐색 순서 출력하기
        print(checked, end = ' ')
        
        # 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
        for i in graph[checked]:
            if not (visited[i]):
                queue.append(i)
                visited[i] = True
                
graph = [
    [],
    [2, 3],
    [1, 4, 5],
    [1, 6],
    [2, 5],
    [2, 4],
    [3]
]

visited = [False] * 7
bfs(graph, 1, visited)

 

DFS (Depth-First Search) - 깊이 우선 탐색

 

깊이 우선 탐색은 다음 분기 (Branch)로 넘어가기 전에 선택된 해당 분기를 완벽하게 탐색하는 방법을 의미합니다. 마찬가지로 모든 노드를 방문하고자 할때 사용되며, 더 이상 탐색할 노드가 없을 때 갈림길이 존재하고 이미 지나친 최근 노드로 돌아와서 다시 새로운 노드를 탐색하는 방석입니다 (자식들을 먼저 탐색)

이를 위해서 방문을 해야할 방문 대기 Stack이 필요하며, 이미 방문을 완료한 Queue가 필요합니다. 시작 노드에서 출발하여 방문을 완료한 노드들은 Queue에 넣어주며, 만약 방문을 해야 하는 노드가 있는 경우 연결된 Node를 방문 예정 Stack에 추가하게 됩니다.

BFS는 방문 대기 Queue에 추가하고 먼저 추가된 노드부터 방문하였는지 체크를 하는 방법이지만, DFS는 방문 대기 Stack에 추가를 하고 가장 나중에 추가된 노드부터 꺼내어서 이미 방문하였는지 확인하는 과정 차이가 존재합니다. 

 

DFS Example

앞서 언급이 되었지만 DFS 구현을 위해서는 스택 자료구조를 이용해야합니다. 

 

 

1. 시작 노드인 1을 스택에 삽입하고 방문 처리를 합니다.

 

 

2. 스택 내 최상단 노드 1에 인접한 노드는 2와 3이며, 번호가 낮은 노드 2를 스택에 삽입하고 방문 처리합니다. 

 

 

3. 스택 내 최상단 노드인 2에 인접한 노드 4, 5중 번호가 낮은 4를 선택하고 스택에 삽입하고 방문 처리합니다

 

4. 스택 내 최상단 노드인 4에 인접한 노드는 5가 있으며 5를 선택하고 스택에 삽입 및 방문 처리 합니다.

 

5. 최상단 노드인 5에 방문하지 않은 인접한 노드가 없으므로 스택에서 5를 꺼내며, 순서대로 4, 2까지 순차적으로 꺼냅니다. 1이 최상단 노드가 되었을 때 방문 이력이 없는 노드 3을 스택에 삽입하고 방문 처리 합니다.

6. 최상단 노드 3에 인접하면서 방문하지 않은 노드 6을 스택에 삽입하고 방문 처리합니다.

 

7.이제 방문하지 않은 노드가 없기 때문에 스택에서 차례대로 꺼냅니다.

 

최종적으로 노드의 탐색 순서 (스택 삽입 순서)는 다음과 같습니다.

1 → 2 → 4 → 5 → 3 → 6

 

DFS Example Code

DFS는 스택 자료구조를 이용하는 알고리즘이며 재귀 함수를 이용하여 간결하게 구성이 가능합니다.

def dfs (graph, node, visited):
    visited[node] = True
    
    print(node, end = ' ')
    
    for i in graph[node]:
        if not (visited[i]):
            dfs (graph, i, visited)
            
graph = [
    [],
    [2, 3],
    [1, 4, 5],
    [1, 6],
    [2, 5],
    [2, 4],
    [3]
]

visited = [False] * 7
dfs(graph, 1, visited)