BFS (Breadth-First-Search)은 너비 우선 탐색 알고리즘의 줄임말입니다.

Graph(그래프)의 너비를 우선으로 탐색한다는게 무슨 말일까요?

필요성

  • 한 node에서 다른 node로 가는 최단 경로(short-path)를 찾을 때
  • 예) 가장 적은 수로 승리하는 게임 방법 계산, 가장 적은 개수의 글자를 고치는 맞춤법 검사기, 가장 가까운 병원 찾기
  • 한 node에서 다른 node로 가는 경로가 존재하는지 알고 싶을 때

정의

BFS (너비 우선 탐색) 알고리즘은 graph(그래프)를 사용해서 최단 경로 문제(short-path problem)를 푸는 방법으로, 답을 찾을 때까지 그래프의 노드에 자식 노드를 타고 들어가며 탐색하는 것을 반복합니다.

  • 현재 노드와 인접한 노드를 먼저 탐색합니다.

  • 답을 찾지 못한 경우, 탐색해야할 목록인 큐(queue)에 현재 노드와 간선 하나로 연결된 자식노드를 추가합니다.
  • 다음 단계에서는 이전 단계에서 큐에 올린 🌟부모 노드의 모든 자식 노드들을 차례로 탐색 🌟합니다.
    • 📌큐의 First-In-First-Out (선입선출) 방식 덕분에 🌟부모 노드의 모든 자식 노드들의 탐색을 완료해야 다음 level에 대한 탐색을 시작🌟합니다. 따라서 시작 노드로부터 목표 노드까지 가는 가장 낮은 level, 즉 최단 경로를 구하게 됩니다.
    • 📌이 부분에서 DFS 알고리즘과 가장 큰 차이가 발생합니다. 🌟DFS 알고리즘은 부모 노드의 모든 자식 노드들의 탐색이 완료되지 않아도 다음 level에 대한 탐색을 시작🌟합니다.
      • DFS 알고리즘은 Last-In-First-Out (후입선출) 방식을 사용하는 스택(stack) 자료 구조를 사용합니다.
      • 따라서 부모 노드의 자식 노드가 여러개라면, 자식 노드를 stack에 저장하고 꺼낼 때 가장 오른쪽에 있는 마지막 자식 노드가 먼저 꺼내지고, 꺼낸 노드의 자식 노드가 또다시 스택에 추가됩니다. 즉, 🌟마지막 자식 노드와 연결된 모든 자식 노드들을 우선 탐색🌟합니다.
      • 그 결과 첫 번째 부모 노드의 나머지 자식 노드들은 탐색되지 못하고 스택에 저장된 채로 남게되며, **마지막 자식 노드에 연결된 모든 자식 노드들의 탐색이 끝나면 저장되어있던 **부모 노드의 나머지 자식 노드들 중 하나의 탐색을 시작합니다.
  • 현재 level에서 답을 찾지 못했다면 다음 level을 탐색하기 위해 자식 노드의 자식 노드를 차례로 탐색하는 과정을 반복합니다.

Queue

Queue(큐)는 자료 구조로 BFS (너비 우선 탐색) 알고리즘이 최단 경로를 찾기 위해 사용합니다.

두 가지 기능이 있습니다.

  • 삽입(enqueue)
  • 제거(dequeue)

Stack과 다른 점

큐는 스택과 비슷하지만 차이점이 있습니다.

스택이 한 쪽 끝에서 삽입과 제거를 모두 처리하느라 나중에 들어간 데이터가 먼저 출력되는 반면,

큐는 나가는 쪽과 들어가는 쪽이 다르기 때문에, 먼저 들어간 데이터가 먼저 나옵니다.

예시

다음 그림은 스택과 큐의 데이터 삽입&삭제 방식을 잊지 못하게 만드는 마법이죠.🧙‍♂️

  • 스택: First-In-Last-Out (후입선출)

  • 큐: First-In-First-Out (선입선출)

구현

구현 방법은 두 가지만 기억하면 됩니다.

  1. 문제를 그래프로 구현한다.
    • 해시 테이블 또는 리스트를 사용해서 이웃 node와의 관계를 기록한다.
  2. 너비 우선 탐색 방법을 사용한다.
    • 큐를 생성하고 큐에 첫 번째 노드 넣기
    • 큐에서 노드 꺼내기
    • 노드의 방문 여부를 조사
      • 목적: 탐색 큐에 같은 노드가 반복해서 추가되어 무한 탐색되는 경우를 방지하기 위함
    • 노드를 방문하지 않았다면 노드를 방문한 것으로 표시하고 자식 노드 탐색 시작
    • 자식 노드 중 방문하지 않은 자식 노드만을 탐색 큐에 추가
    • 탐색 큐에 있는 노드가 없어지거나 답을 찾을 때까지 위의 과정 반복
# Make Graph
input = sys.stdin.readline
n, m, v = map(int, input().split()) # n:node개수, m:edge개수, v:시작 node

graph = [[] for _in range(n)]	# node 개수 만큼 빈 list를 만들어준다.
for _ in range(m):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)	# node에 연결된 자식 node를 기록한다.
    graph[n2].append(n1)
    
def bfs(v):
    q = deque([v])
    visited = []
    while q:    #큐에 노드가 없을 때까지 반복
      	node = q.popleft()
        if node not in visited: #방문하지 않은 노드만 방문한다.
          visited.append(node) #노드를 방문한 것으로 기록한다.
          for child in sorted(graph[node]):
          if child not in visited:    #방문하지 않은 자식 노드를 큐에 추가한다.
                    q.append(child)
    return visited

예시

서로 연결된 사람들 중에 이름이 d로 시작하는 사람이 존재하는지 확인하는 문제를 가정해볼게요.

from collections import deque

graph = {} # 해시 자료형 사용
graph['me'] = ['mom', 'dad', 'sister'] # graph의 'me' 노드와 연결된 노드인 'mom', 'dad', 'sister'를 기록합니다.
graph['sister'] = ['frend1']
graph['frend1'] = ['friend2']
graph['frend2'] = ['me']

def search(name):
    search_queue = deque()  # 탐색할 목록
    search_queue += graph['me']  # 탐색을 시작할 노드를 탐색 목록에 추가
    searched = []  # 이미 탐색한 노드 목록

    while search_queue:  # 탐색 큐에 데이터가 없을 때가지 반복
        persion = search_queue.popleft()  # 탐색 큐에서 가장 먼저 들어간 노드를 꺼냄
        if persion not in searched: # 노드가 이미 탐색한 노드 목록에 포함되지 않는 경우에만 탐색 시작
            if persion[0] == 'd': # 정답을 찾을 경우
                return True # 답이 있음을 반환
            else:   # 해당 노드에 정답이 없는 경우
                search_queue += graph[persion]  # 현재 노드의 자식 노드들을 탐색 목록에 추가
                searched.extend(persion)    # 탐색을 완료한 현재 노드를 탐색 완료 목록에 추가
    # 모든 노드를 탐색 완료해서 탐색 큐에 데이터가 없을 때 while loop가 종료됨
    return False    # 답이 없음을 반환