[BFS] 이것이 코딩테스트다

BFS = Breath First Search 너비 우선 탐색

가장 가까이에 있는 노드부터 우선 탐색

일반적인 경우 실제 수행시간은 DFS보다 좋다.

collections 모듈의 deque 라이브러리를 사용한다.

예제 코드

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
  # 큐 구현을 위해 deque 라이브러리 사용
  queue = deque([start])
  # 탐색한 노드를 방문처리
  visited[start] = True
  # 큐가 빈 상태가 될 때까지 반복
  while queue:
    v = queue.popleft()
    print(v, end = ' ')
    # 탐색한 노드와 연결되어 있지만 아직 안 읽은 노드들을 큐에 삽입
    for i in graph[start]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True

graph = [
    [],
    [2,3,8],
    [1,7],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False]*9

bfs(graph, 1, visited)