BFS

큐를 사용하는 것보다 deque 를 이용해 큐처럼 사용하는게 편하다.
방법
왼쪽에서 입/출력: appendleft(val), popleft()
오른쪽에서 입/출력: appeend(val), pop()
(오른쪽에서의 입/출력이 기본이고 왼쪽인 경우 'left' 가 붙는다.)

주의 사항
큐에 삽입 => 실제 방문

큐에 삽입 시 실제 방문을 할 수 있는 이유
방문가능지역 검사에서 만난 순서와 실제 탐색 지역의 순서가 일치하기 때문

# BFS
from collections import deque
def bfs(graph, r, visited):
    # 큐 사용
    queue = deque()
    # 큐에 시작 노드 삽입 & 방문 처리
    queue.append(r)
    visited[r] = True
    print(r)
    # 큐가 빌때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]: # 인접한 노드중 방문하지 않은 노드를 "모두" 큐에 넣음
                queue.append(i) # 삽입
                visited[i] = True # 방문 처리
                print(i)