[알고리즘] 큐를 이용해 BFS 구현하기 (python)

오늘은 BFS 구현에서 주로 사용하는 큐에 대해 포스팅하고, 관련 적용 사례를 복습해보려고 한다. 사실 BFS/DFS 문제를 풀다보면 나는 DFS에 훨씬 더 익숙해서, DFS로 주로 풀이를 한다. 그 이유가 BFS 구현에서 큐에서 막히기 때문이라고 생각했고, 관련 포스팅을 하게된 것이다! 

 

# 큐(Queue)

우선 큐는 쉽게 말해서 다음과 같은 선입선출 구조이다. 먼저 들어온 요소가 먼저 나가는, 그런 것이다. 

BFS(너비우선탐색) 구현에는 큐를 이용하는 것이 정석인데, 그 이유는 BFS는 인접한 노드부터 차례로 넓게 탐색하는 알고리즘이기 때문이다. (BFS에 대해서는 따로 설명하지 않겠다) Python에는 친절하게도 deque 라이브러리가 존재해서, 큐 자료구조를 이용하고 싶을 때는 관련 라이브러리를 다음과 같이 import 해 이용하면 된다. 

from collections import deque

 

그리고 큐에 원소를 넣을 때는 리스트처럼 append, 가장 먼저 들어온 원소를 빼고싶을 때는 popleft()를 이용하면 된다. 큐를 생성할 때는 deque( 원소 ) 로 생성하면 된다.  

from collections import deque

q = deque()    # deque 객체 > list 변환도 가능
q.append(5)
q.append(2)
q.append(3)
q.append(7)

q.popleft()    # 가장 먼저 들어온 5가 삭제된다

q.append(1)
q.append(4)

q.popleft()    # 그 다음 들어온 2가 삭제된다

print(q)       # 먼저 들어온 순서대로 출력된다

 

# 예제

그럼 앞선 deque 라이브러리를 이용해 BFS가 어떻게 구현되는지 살펴보자. 구현의 메인 아이디어는 다음과 같다.
매번 인접한 노드를 큐에 넣었다가, 선입 선출로 차례차례 빼는 것 !
그림으로 나타내면 다음과 같이 나타날 수 있겠다. 

위 그림과 같은 과정(인접노드들을 큐에 넣고 하나하나 꺼내며 그 노드들의 또 다른 인접노드를 큐에 또 넣기) 을 큐가 빌 때까지 반복하면, BFS 과정이 완성된다. 이러한 과정을 Python 코드로 나타내면 다음과 같다. 단, visited를 체크해주는 것을 잊지 말아야한다!

from collections import deque

def bfs(graph, start, visited):

  q = deque([start])
  visited[start] = True    # 현재 시작 노드 방문 처리

  ## 큐가 빌때까지 반복하기
  while queue:

    # 큐에서 가장 예전에 들어온 원소 하나 뽑기
    v = q.popleft()
    print(v, end=" ")

    # v의 인접 노드 순회
    for i in graph[v]:

      # 방문하지 않은 노드는 큐에 append
      if not visited[i]:
        q.append(i)
        visited[i] = True

 

# 적용하기 

이러한 BFS 구현에서 큐를 사용하는 예시는 정말 다양하지만, 지금까지 풀이했던 문제 중 네트워크(프로그래머스)

2022.03.15 - [Algorithms 💻] - [프로그래머스] 네트워크 (python) - BFS/DFS

문제를 다시 보도록 하겠다. 

 

 

 

 

References 

[1] https://somjang.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9C%BC%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%81%90-Queue