너비 우선 탐색(BFS)

BFS(너비 우선 탐색)

1. BFS(Breadth-First Search)란?

---

BFS알고리즘은 너비 우선 탐색이란 의미를 가진다. 이는 가까운 노드부터 탐색하는 알고리즘이란 뜻이다.

DFS는 최대한 멀리있는(깊은) 노드부터 탐색하는것에 비해 BFS는 가까운 노드부터 탐색하므로 이 두개를 적절하게 사용해야 한다.

BFS 구현에서는 선입선출, 즉 큐 자료구조를 사용하는것이 정석이다.

---

 BFS 알고리즘의 동작방식에는  
 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.  
 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.  
 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.  

2. 예시 코드

---

from collections import deque  

def bfs(graph, start, visited):  
  q = deque([start])                  # q선언 (start를 첫 인자로 넣음)  
  visited[start] = True               # 방문 표시  
  while q:                          # q가 빌때까지  
    v = q.popleft()                   # 가장왼쪽(가장먼저)원소 뽑아서 v에 대입  
    print(v, end = ' ')  
    for i in graph[v]:  
      if not visited[i]:  
        q.append(i)  
        visited[i] = True  

n = int(input())                      # 노드의 개수  
graph = [[] * (n + 1)]  

for _ in range(1, n+1):  
  array = list(map(int, input().split()))  
  graph.append(array)  

visited = [False] * (n + 1)         #[0]은 사용 x  

bfs(graph, 1, visited)  

3. 예시 입출력

  (같은 행은 해당행의 index와 연결된것이다. (노드1은 노드2,노드3,노드8과 연결))

  입력:
  (노드1)  2 3 8  
  (노드2)  1 7  
  (노드3)  1 4 5  
  (노드4)  3 5  
  (노드5)  3 4  
  (노드6)  7  
  (노드7)  2 6 8  
  (노드8)  1 7  

  출력:
  노드 1에서 bfs를 구하면  
  output = 1 2 3 8 7 4 5 6