[알고리즘] BFS / DFS 분석 및 비교 + Python 구현

그래프에서 노드를 탐색하는 두 알고리즘 DFS와 BFS에 대해 정리하고자 글을 작성한다.

BFS(Breadth-First Search) 요약

BFS는 하나의 node에서 인접한 node를 Queue에 저장시켜놓는다.

그리고 더 이상 방문 가능한 인접 node가 없을 때 FIFO(First In First Out)를 통해 하나의 인접 node를 pop 시켜 정점을 이동한다.

해당 node에서 또 인접한 node를 Queue에 저장시켜, 결과적으로 Queue에 더 이상 저장된 node가 없을 때 까지 Searching하는 방식이 BFS이다.

하나의 Node에서부터 방문 가능한 주변 Node들을 모두 찾아나가면서 조사하는 것이다.

 

DFS(Depth-First Search) 요약

DFS는 재귀함수를 이용하여 하나의 Node에서 이동가능한 인접 Node로 반복 이동시켜 Node를 통해 이동할 수 있는 최대한 깊이 탐색을 하고 return을 한다. 그리고 다시 돌아가 가능한 다른 경로를 또 탐색하는 방식이다.

핵심은 노드 방문 여부를 저장하는 boolean list 를 사용하여 중복하여 DFS가 반복되지 않도록 하는 것이다.

이는 어떻게 보면 BFS에서도 이미 방문했던 인접 노드에서 또 BFS가 반복되는 것을 막기 위해서도 사용해야 하는 것 같다.

 

이해를 돕기 위해 BFS와 DFS 관련 이미지를 첨부하고 싶지만 저작권 문제도 있고 직접 그리기엔 여유도 없어서 생략하고 알고리즘 정리하겠다.

코드는 복잡하지 않다.

 

BFS 코드 [ O(V+E) ] 

BFS는 최초 점으로부터 adjacency list를 이용해서 주변 node를 queue에 저장하고 pop하는 FIFO방식으로 node를 탐색하도록 구현해주면 된다.

 

DFS 코드 [ O(V+E) ] 

DFS는 방문했던 점인지만 판단을 해서 dfs 함수를 재귀 함수 형태로만 구현을 해주면 된다.

 

위  두 코드는 adjacency list를 사용하여 O(V+E)의 시간 복잡도를 가진다.

Adjacency list와 visited boolean list를 잘 구현해주면

두 알고리즘 모두 간단하게 구현될 수 있다.

다만 어떤 문제에서 어떤 것을 요구하냐에 따라 천차만별로 응용되는 듯 하다.

특정 노드 간 최단 거리를 구해야할 수도 있고, Partition이 어떻게 나뉘는지도 알아내야할 수도 있고

위 코드는 결국 엄청 기초적인 뼈대만을 제시한다.

문제를 풀 때 필요한 알고리즘을 꿰뚫고 살을 잘 붙여서 적절하게 잘 쓰는 능력을 길러야 할 것 같다.

 

개인적으로 BFS와 DFS를 쓰기 전에 굉장한 고민이 들 때 또는.. BFS로 기껏 구현했는데 DFS로 푸는게 유리하다거나.. 그런 경우들을 많이 경험했기에..

어떤 경우에서 어떤 알고리즘을 쓰는게 유리한지 GPT 힘을 빌려서 아래에 적겠다.

아래는 내가 적은 글이 아니다.

BFS와 DFS는 각각 다른 상황에서 유리합니다.

BFS는 시작 노드에 가까운 정점을 검색하는 데 더 적합합니다.

예를 들어, 최단 경로 문제에서 BFS를 사용하여 시작 노드에서 목표 노드까지의 최단 경로를 찾을 수 있습니다.

또한, BFS는 너비 우선 탐색이므로, 트리의 각 레벨을 순차적으로 탐색하며, 각 레벨의 모든 노드를 방문합니다.

이러한 특성 때문에 BFS는 트리의 최소 깊이를 찾는 문제에 적합합니다.

 

반면, DFS는 소스에서 멀리 떨어진 해결책이 있는 경우 더 적합합니다.

예를 들어, 게임이나 퍼즐 문제에서 결정 트리를 사용하는 경우 DFS가 더 적합합니다.

DFS는 깊이 우선 탐색이므로, 트리의 한 가지 분기를 가능한 한 깊게 탐색한 다음 되돌아갑니다.

이러한 특성 때문에 DFS는 트리의 최대 깊이를 찾는 문제에 적합합니다.