[알고리즘] 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)

BFS, DFS는 여러 그래프 탐색 문제를 해결할 때 가장 흔히 사용되는 알고리즘들 중 하나이다.

그래프 탐색 문제란 어떤 한 그래프와 해당 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선을 타고 이동할 수 있는 정점들을 모두 찾아야 하는 문제를 말한다.

 

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

깊이 우선 탐색(DFS)은 그래프의 시작점에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색한다.

알고리즘의 개요는 시작점에서 시작점에 연결된 정점 -> 위 정점에 연결된 정점 ... 식으로 해당 브랜치에 연결된 간선이 없을 때까지 탐색한 후 다시 되돌아가 방문하지 않은 정점이 없을 때까지 위 방식을 반복하게 된다.

 

(1) 깊이 우선 탐색 구현

 

DFS를 구현할 때는 직전에 방문했던 정점을 기억하고 있어야 하기 때문에 스택(Stack)을 많이 사용하는 편이다.

하지만 list에서 pop을 사용하면 성능면에서 떨어지는 단점이 있어 collections 패키지의 deque도 많이 사용한다고 한다!

깊이 우선 탐색 알고리즘을 코드로 나타내면 다음과 같다. 

그래프의 표현 방식에 따라 코드가 조금씩 바뀔 수 있다. 

graph_list = {1: set([3, 4]),
              2: set([3, 4, 5]),
              3: set([1, 5]),
              4: set([1]),
              5: set([2, 6]),
              6: set([3, 5])}
root_node = 1

def DFS(graph, root): # 탐색할 그래프, 시작점을 인수로 받음
    visited = []
    stack = [root]

    while stack:
        n = stack.pop()
        if n not in visited: # stack에 든 노드가 아직 방문하지 않은 노드라면
            visited.append(n) 
            stack += graph[n] - set(visited) # stack에 방문한 노드를 제외하고 추가!
    return visited
print(DFS(graph_list, root_node))

DFS에서 데이터를 찾을 때는 "앞으로 찾아야 할 노드"와 "이미 방문한 노드"를 기준으로 데이터를 탐색한다.

특정 노드가 앞으로 찾아야 할 노드라면 계속 탐색하면 되고, 이미 방문한 노드이면 무시하거나 지나가면 된다.

 

(2) 깊이 우선 탐색 알고리즘의 분석

 

깊이 우선 탐색 알고리즘에서는 어떤 형식으로 그래프를 저장하냐에 따라 시간복잡도가 달라진다.

인접 리스트를 사용할 경우 리스트 노드를 한번씩 조사해야 하며, 리스트 노드의 수는 2e개 이므로 O(e) 시간이 걸린다.

인접 행렬을 사용할 경우 한 정점에 인접한 정점들을 조사하기 위해 O(n) 시간이 걸리며 전체 원소들을 조사해야 하므로 O(n^2) 시간이 걸린다.

 

* 인접 행렬은 노드와 간선의 정보를 행렬도 표현하는 방법으로 간선과 상관없이 모든 노드를 표현하므로 노드의 수가 많을수록 메모리 사용량이 늘어난다. 

* 인접 리스트는 노드와 간선의 정보를 기스트로 표현하는 방법으로, 간선으로 연결된 것만 표시하므로 인접 행렬에 비해 간단한 편이다.

2. 너비 우선 탐색

너비 우선 탐색(BFS)은 그래프의 시작점에서 가까운 정점부터 우선적으로 탐색한다.

알고리즘의 개요는 시작점에서 시작점에 인접한 정점들을 모두 탐색한 후 시작점의 자식노드에서 해당 과정을 반복하면 된다. 

 

(1) 너비 우선 탐색 구현

 

BFS를 구현할 때는 큐(Queue)를 많이 사용하고 있다.

파이썬에서 큐는 리스트 타입을 통해서 쉽게 구현할 수 있지만, 위에서도 말했듯이 deque로 구현하면 시간적으로 더 효율적이다.

너비 우선 탐색을 코드로 나타내면 다음과 같으며, 함수 입력값은 깊이 우선 탐색 구현 시 사용한 값과 동일하다.

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

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited

print(BFS(graph_list, root_node))

(2) 너비 우선 탐색 알고리즘의 분석

 

너비 우선 탐색 알고리즘에서는 어떤 형식으로 그래프를 저장하냐에 따라 시간복잡도가 달라지며 깊이 우선 탐색과 동일하다.

인접 리스트를 사용할 경우 리스트 노드를 한번씩 조사해야 하며, 리스트 노드의 수는 2e개 이므로 O(e) 시간이 걸린다.

인접 행렬을 사용할 경우 한 정점에 인접한 정점들을 조사하기 위해 O(n) 시간이 걸리며 전체 원소들을 조사해야 하므로 O(n^2) 시간이 걸린다.

 

마지막으로 다시 정리하면

깊이 우선 탐색(DFS)는 스택 / 너비 우선 탐색(BFS)는 큐!

 

코드 진행 순서를 간략화하면

1. visited, queue/stack 선언 및 초기화

2. queue/stack이 비어있지 않다면 pop -> visited 했는지 확인

    2-1. visited 했다면 : while문으로 돌아가 반복

    2-2. visited 하지 않았다면 : pop한 값을 visited에 넣고, queue/stack에 pop과 이어진 정점들 넣기

3. while 반복문이 끝나면 원하는 값(ex. visited) return 하기