[BFS] BFS 알고리즘의 개념 및 동작과정 / DFS와 BFS 선정 기준

BFS는 Breadth-First Search, 너비 우선 탐색이라고 부르며 가까운 노드부터 탐색하는 알고리즘이다.

 

 

BFS 구현에서는 선입선출 방식인 Queue 자료구조를 이용하는 것이 정석이다.

인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

 

BFS 알고리즘의 동작 과정

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

너비 우선 탐색 알고리즘인 BFS는 Queue 자료구조에 기초한다는 점에서 구현이 간단하다.

 

실제로 구현 함에 있어 앞서 언급한 대로 deque 라이브러리를 사용하는 것이 좋으며, 탐색을 수행함에 있어 “O(N)”의 시간이 소요된다.

일반적으로 실제 수행 시간은 DFS보다 좋은 편이다. (BFS > DFS)

 

from collections import deque

#BFS 메소드 정의
def bfs(graph,start,visited):
    # Queue 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    
    # 현재 노드를 방문 처리
    visited[start]=True

    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아서 출력
        v = queue.popleft()
        print(v,end=' ')

        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True

DFS와 BFS에 대한 비교

앞서 DFS와 BFS를 설명하는데 전형적인 그래프 그림을 이용했지만 1차원 배열이나 2차월 배열 또한 그래프 형태로 생각하면 수월하게 문제를 풀 수 있다. 특히나 DFS와 BFS 문제 유형이 그러하다.

 

 

DFS vs BFS

DFS와 BFS를 공부할 때마다 어떠한 상황에서 어떤 알고리즘을 사용해야할지 잘 감이 오지않아 검색해본 결과, 모든 경우의 수를 탐색해봐야 하는 경우에는 DFS를, 깊이(Depth)를 계산해야 하는 경우에는 BFS를 사용하는 것이 적절하다고 한다 :)

 

DFS
1) 연결된 그래프를 완전 탐색하는데 활용가능
2) 모든 경우를 하나하나 다 탐색을 해야될 경우 이용(위의 예의 경우 조합, 순열 모든 경우의수를 하나한 다 찾고자할때)
3) 위의 개념과 결부된 깊이 우선탐색이라는 개념을 가진 순열, 조합 구현에 활용

BFS
1) DFS와 마찬가지로 연결된 그래프를 완전탐색하는데 활용
2) depth(깊이)를 계산해야되는 문제에 활용(최단경로의 길이 == depth(깊이))
3) 위의 개념과 결부된 가중치가 같은 그래프에서 최단거리를 찾는데 활용

 

1) 그래프의 모든 정점을 방문해야하는 문제
DFS, BFS 뭐든 상관없다. 편한걸 쓰면 된다.
 
2) 경로의 특징을 저장하는 문제
예시로 각 정점에 숫자가 있고 a부터 b까지 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제. 각각의 경로마다 그 특징을 저장해두어야하는 문제는 DFS를 사용한다.
 
3) 최단거리를 구하는 문제
미로찾기등 최단거리를 구하는 경우 BFS가 좋다. DFS로 경로를 탐색하면 처음 발견하는 해답이 최단거리가 아닐수도 있지만 BFS는 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색시 먼저 찾아지는 해답이 곧 최단거리다.
 
4) 검색 대상 그래프가 많이 클 경우에는 DFS가 좋다고한다.
 
5) 검색 대상의 규모가 별로 크지않고 검색 시작지점으로부터 원하는 대상이 별로 멀지 않으면 BFS.

 

(출처 : https://foameraserblue.tistory.com/188?category=481823 , https://duckracoon.tistory.com/entry/DFS%EC%99%80-BFS-%EA%B0%81%EA%B0%81-%EC%82%AC%EC%9A%A9%ED%95%98%EB%8A%94-%EA%B2%BD%EC%9A%B0)

DFS와 BFS 각각 사용하는 경우

PS를 하며 느끼는 DFS와 BFS 선택의 기준