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
    # 큐가 빌때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end =' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]: # 인접한 노드중 방문하지 않은 노드를 "모두" 큐에 넣음
                queue.append(i) # 삽입
                visited[i] = True # 방문 처리