2021.11.13 코테_BFS 예시코드

# 오늘의 문제

BFS ( Breadth-First Search) 예시코드 

# BFS 

너비우선 탐색 - 그래프 ( 간선과 노드로 이루어진) 라는 자료구조를 탐색하는 문제가 많이 출제된다. 거기에서 사용하는 알고리즘이라고 표현할 수 있겠다.

아래의 코드는 해당 그래프를 BFS 로 탐색하는 방법의 예시를 코드로 옮겨 놓은 것이고 이로써 직접 작성해보며 BFS 에 대한 이해를 높이기 위해 서술 해두었다.

 

from collections import deque

def bfs(graph, start, visited):
  queue = deque([start])

  visited[start] = True

  while queue:
    #이부분에 print(queue) 하면 이해가 쉽다.
    v = queue.popleft()
    print(v, end=' ')

    #이 부분이 큐를 활용해서 BFS를 구현하는 핵심이라 볼 수 있다.
    # [1] -> [1,2,3,8] 들어가면 1빼고 루프 2빼고 루프
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True


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

visited = [False] * 9

bfs(graph, 1, visited)