[Python] BFS(Breadth First Search) 알고리즘

*해당 포스팅은 이것이 코딩 테스트다 with python(나동빈 지음) 교재를 공부하며 작성한 글입니다.

 

 

 

안녕하세요! 오늘은 탐색 알고리즘 중 하나인 BFS 알고리즘에 대해 알아보겠습니다.

 

BFS란 'Breadth First Search'의 약자로 너비 우선 탐색이라고 불리며, 그래프에서 가까운 부분을 먼저 탐색하는 알고리즘입니다.

 

BFS 알고리즘은 주로 최단거리를 구할 때 사용합니다.

 

BFS 알고리즘을 이해하기 위해서는 큐 구조와 그래프의 구조에 대해 알아야 합니다.

 

그래프에 대해서는 이전 DFS 알고리즘 포스팅에서 설명드렸으니 넘어가고 큐 구조에 대해 설명드리겠습니다.

 

 

큐(Queue)

 

큐는 선입선출(First In First Out)의 구조입니다. 큐의 구조는 편의점에서 물품을 진열하는 방식과 같습니다.

 

편의점에서 새로 들어온 물건을 진열할 때는 기존의 물건들보다 뒤쪽에 진열합니다.

 

이전 물건들이 먼저 팔릴 수 있도록 하기 위함입니다.

 

큐도 이와 같습니다. 

 

그림으로 보면 다음과 같습니다.

 

 

큐 구조

 

 

파이썬에서는 큐에 데이터를 삽입할 때 queue.append() 메서드를 사용하고 삭제할 때는 queue.popleft() 메서드를 사용합니다.

 

 

이제 BFS 알고리즘에 대해 자세히 알아보겠습니다. BFS의 동작 방식은 다음과 같습니다.

 

 

① 탐색을 시작할 노드를 큐에 삽입하고 방문 처리를 한다.

 

② 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 

 

③ 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

 

코드로 이 과정을 알아보겠습니다.

 

 

from collections import deque

visited =  [False]*9

def bfs(graph, start, visited):
    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 알고리즘과 많이 비슷합니다.

 

반복문 내부만 살짝 다릅니다.

 

visited 리스트는 방문처리를 할 리스트를 뜻합니다.

 

graph는 자신이 원하는 대로 2차원 리스트 자료형으로 입력하면 됩니다.

 

반복문에서는 현재 노드(v)의 인접한 노드(i) 중 방문하지 않은 노드가 있다면 큐에 삽입하고 해당 노드를 방문 처리합니다.

 

일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있다면 번호가 낮은 순서부터 처리합니다.

 

BFS 알고리즘은 큐 자료구조에 기초한다는 점에서 구현이 간단합니다.

 

또한 재귀 함수를 사용하는 DFS 알고리즘에 비해 더 빠르게 동작합니다.

 

 

 

지금까지 BFS 알고리즘에 대해 알아보았습니다.