[BFS] BFS 기본 구성

[문제]

- BFS 알고리즘의 기본을 구성해본다

 

[아이디어]

- DFS 는 재귀함수 형태로 만들어진다. 스택 자료구조로 만들어진다.

- BFS 는 큐 자료구조로 만들어진다.

- DFS 와 BFS모두 시간복잡도는 O(N) 으로 동일하지만, 일반적으로 실제 수행시간은 BFS가 빠르다고 본다. (재귀함수의 이용으로 인한 컴퓨터의 동작시간으로만 언급되고 있으며, 너무 깊어지는 내용이므로 일반적인 수행시간으로만 알고있도록 하자)

 

# deque 라이브러리를 이용
from collections import deque

def bfs(graph, start, visited):
  # 큐의 구현을 위해 deque 라이브러리를 이용한다.
  queue = deque([start])

  # 현재노드 방문처리
  visited[start] = True

  # 큐가 빌때까지 반복한다
  while queue:
    # 큐의 원소를 pop
    v = queue.popleft()
    print(v, end=' ')

    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True

graph = [
  [],       # 0번은 존재하지 않는다
  [2,3,8],  # 1번 주변정보
  [1,7],    # 2번 주변정보
  [1,4,5],  # 3반 주변정보
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]    # 8번 주변정보
]

visited = [False] * 9

bfs(graph, 1, visited)

 

[해설]

- 큐를 이용하여 방문했던 graph 를 체크하는식으로 알고리즘을 만들었다.

- graph 대신 배열이 주어지면 더 쉬운방식으로 문제의 해결이 가능하다고한다.