9. 너비우선 탐색

#1. 너비우선 탐색(Breadth-First Search)
* BFS : 대표적인 그래프 탐색 알고리즘
* 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 우선 탐색하는 방식
* 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회함

graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

graph
-->
{'A': ['B', 'C'],
 'B': ['A', 'D'],
 'C': ['A', 'G', 'H', 'I'],
 'D': ['B', 'E', 'F'],
 'E': ['D'],
 'F': ['D'],
 'G': ['C'],
 'H': ['C'],
 'I': ['C', 'J'],
 'J': ['I']}
 
 
 * 방문했던 리스트
  - A, B, C, D, G, H, I, E, F, J

* 방문 해야할 리스트
  - A : B, C
  - B : C, A, D
  - C : A, D, A, G, H, I
  - D : A, G, H, I, B, E, F
  - G : H, I, B, E, F, C
  - H : I, B, E, F, C, C
  - I : B, E, F, C, C, C, J
  - E : F, C, C, J, D, D
  - J : D, D, I


예시
1)
data = [1,2,3,4]
data.pop()
print(data)
data.pop(0)
print(data)
temp = data.pop(0)
print(data, temp)
-->

[1, 2, 3]
[2, 3]
[3] 2


2) 
data = [1,2,3,4]
data.extend([4,5])
print(data)

-->
[1, 2, 3, 4, 4, 5]


def bfs(graph, start_node):
  visited, need_visit = list(), list()
  need_visit.append(start_node)

  while need_visit:
    node = need_visit.pop(0)
    if node not in visited:
      visited.append(node)
      need_visit.extend(graph[node])
    return visited

bfs(graph, 'A')
-->
['A']


#2. 깊이 우선 탐색(Depth-first Search)
* DFS : 대표적인 그래프 탐색 알고리즘
* 정점의 자식들을 먼저 탐색하는 방식
* 한 노드의 자식을 타고 끝까지 순환한 후 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회함


예시)
def dfs(data, start_node):
  visited, need_visit = list(), list()
  need_visit.append(start_node)

  while need_visit:
    node = need_visit.pop()
    if node not in visited:
      visited.append(node)
      need_visit.extend(graph[node])
    return visited