[ Python ] BFS 너비 우선 탐색과 DFS 깊이 우선 탐색 ( 2 )

앞서 소개했던 DFS ( Depth First Search ) 깊이 우선 탐색을 이어서 오늘 소개하고자 하는 알고리즘은 BFS ( Breadth First Search ) 이다.
만약에 우리 인간에게 다음 사진과 같은 트리를 주고 노드의 개수를 세어보라고 한다면, 다수가 BFS 와 같이 개수를 셀 것이다. 대다수의 문자가 가로쓰기를 기본으로 하기에 위에서 아래로 그리고 왼쪽에서 오른쪽으로 눈으로 읽는게 체화되어있다. 노드를 문자처럼 한 줄 단위로 넘어가는식으로 이해를 하니 이해도 빠르고, 알고리즘을 짜보는데도 큰 도움이 되었다.

우리가 앞에 살펴보았던 DFS 는 스택 자료구조와 유사하게 구현이 된다는 사실을 알고있다. 반면에 오늘 살펴보고자 하는 BFS 는 큐 자료구조와 유사함을 갖고, 실제로 코드를 구현할때에도 큐 자료구조를 사용한다.

큐 자료구조의 특징과 장점은 선입선출 ( 先入先出 ) 먼저 들어온 데이터가 먼저 나간다는 점과 데이터를 넣고 뺄때의 속도가 상당히 빠르다는 점을 가지고 있다.
BFS 알고리즘의 순서는 다음과 같다.

1 . 1번노드에 해당하는 초기 노드값을 입력하여 방문한다.
2 . 현재 방문중인 노드와 인접한 노드 중 낮은 숫자를 우선적으로 큐에 입력한다.
3 . 더이상 현재 방문중인 노드와 인접한 노드가 없다면, 큐에 남은 데이터 중 가장 먼저 입력된 값을 pop 하고 방문한다
4 . 방문하지 않은 노드가 없을때까지 2-3을 반복한다.

간단하게 요약한 BFS 알고리즘은 위와 같다. 조금 찬찬히 들여다보면, 루프가 생길 경우는 어떻게 처리할 것인지에 대한 의문점이 생길 수 있다 DFS 와 같이 방문처리 리스트를 만들어도 상관없다. 하지만, BFS알고리즘은 대부분 1번노드에서 원하는 노드까지의 거리를 구할 때 사용된다.
그 경우 1번 노드에서 해당 노드까지의 거리가 계산될것이다. 만약 해당 노드를 재방문 시 루프가 생겼다면, 해당 노드까지의 거리가 루프 판별에 사용된다. 현재 입력된 거리보다 새로 입력된 거리가 짧다면 새로 입력된 트리에 노드를 종속시키고, 그렇지 않다면 해당 노드를 방문하지 않으면 된다.

from collections import deque
# 큐 Queue 구현을 위해 deque 라이브러리 사용

visited = [[False] for _ in range(len(nodes))]

def bfs(Data, Start_node, visited):
    queue = deque([Start_node_node])
    # 현재 노드 방문처리
    visited[Start_node] = True
    # queue 가 빌때까지 반복
    while queue:
        # queue 에서 하나의 원소를 뽑아 방문
        v = queue.popleft()
        for i in Data[v]:
            if not visited[i]: #만약 해당 노드에 방문하지 않았다면?
                queue.append(i)
                visited[i] = True # 방문처리

BFS 알고리즘의 방문처리 리스트를 사용하는 함수 코드는 대략 위와 같다. 단순히 방문처리를 해야만 한다면 방문리스트를 Boolean 자료형으로 만들어서 확인하는것 만으로도 충분할것이다. 하지만 앞서 소개했듯이, Start_node 에서 원하는 노드까지의 거리를 구할 때 자주 사용되는 알고리즘인 만큼, 루프의 생성 여부는 시작노드에서 해당노드까지의 최소거리를 판별하는 방식으로 하는것이 더욱 중요할 듯 하다. DFS 와 대조되는 장점이라면, 너비를 우선으로 탐색하기에 노드까지의 경로가 여러개여도 최단거리를 쉽게 판별할 수 있다. 하지만, 노드의 수가 많아지거나 깊이가 깊은 해가 있을경우엔 오히려 느릴 수 있고 스택 자료구조와 다르게 큐 자료구조를 사용하여 당장 사용하지 않는 자료들 또한 저장하므로 저장곤간의 여유가 필요하다.

[[ 마무리 ]]
Python 과 많은 알고리즘 테스트에서는 queue 자료구조를 매우 빈번하게 사용한다. 상당히 직관적일 뿐만 아니라, 앞서 말했듯이 데이터의 읽고 쓰는 속도가 다른 자료구조에 비해 상당히 빠르므로, 시간을 중요시 여기는 테스트에서 직관적으로 코딩이 가능할 뿐더러 구동속도까지 빠른 queue 의 빈번한 사용은 어쩌면 당연한 일 일지도 모르겠다. 메모리의 여유또한 대다수의 코드에서는 메모리까지 신경 쓸 일이 많지 않아 큰 단점으로 다가오지 않는다.
아마도 다음에 업로드 할 내용은 정렬이 될 듯 싶다.