Algorithms-[BFS]

오늘은 BFS 너비우선탐색에 대해서 설명하겠다. 저번 DFS에서 간단하게 말했었는데 다시 설명하겠다. DFS와 구별하면서 이해하는게 훨씬 쉽다. DFS는 한분기의 끝까지 탐색하고 아니면 돌아오고 다시 끝까지가고를 반복하는데, BFS는 "너비" 우선탐색이므로 한단계를 전부 탐색하고 다음 깊이로 들어간다. 즉 루트로부터 가까운 애들을 먼저 탐색한후 점점 멀어진다. 너비우선탐색은 최단경로나 임의의 경로를 찾을 때 쓰인다. DFS는 재귀로 구현을 했는데, WBS는 보통 QUE를 의 선입선출을 이용해서 코드를 구현한다. 이때 주의할점은 반드시 방문한 노드를 기억하는 코드가 있어야된다는 곳이다. 방문만하고 기억하지않으면 무한루프에 빠지게 된다. 

from collections import deque

def bfs(graph, start):
    visited_nodes = []
    adjacency_nodes = deque([start])

    while near_nodes:
        node = near_nodes.popleft()
        if node not in visited_nodes:
            visited_nodes.append(node)
            near_nodes.extend(graph[node])

    return visited_nodes

아 추가로 deque를 import해서 사용했는데, 기본 queue는 매우 느리고 시간 초과의 원인이되므로 반드시 파이썬에서는 deque를 사용하는 것을 권장한다고 한다. deque와 queue의 차이점은 queque는 방향이 정해져있어 한쪽으로는 입력만, 반대쪽으로는 출력만 가능한데, deque는 양쪽에서 입출력이 가능하다고 한다.