1. BFS

• 그래프를 탐색하는 방법 중 하나로, 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조 혹은 Linked List를 이용한다.
• 그래프의 최단 경로를 구하는 다익스트라 알고리즘 등에 유용하게 쓰인다.
• 대표 유형 : 경로 탐색, 네트워크, 조합 만들기

2. 동작 원리

from collections import deque

# 1. 큐에 시작 위치를 넣고 방문 처리를 한다.
queue = deque([1]) 
visited = [1]

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

while queue: # 큐가 빌 때까지 진행한다.
    x = queue.popleft() # 2. 큐에서 원소를 꺼낸다.
    for node in graph[x]: #3. 연결되어있는 노드들을 확인하는데
        if node not in visited: #4. 방문하지 않은 노드가 있다면
            queue.append(node)  # 5. 큐에 넣고
            visited.append(node) # 6. 방문 처리를 한다.
print(visited)

3. 주의할 점

1. BFS는 재귀로 동작하지 않는다.
2. 시작점에 방문했다는 표시를 남겨야 한다.
3. 큐에 넣을 때 방문했다는 표시를 해야지, 큐에서 빼낼 때 방문했다는 표시를 남기면 안된다.
4. 이차원 배열인 경우 연결된 원소가 범위에 벗어났는지 체크해야 한다.