[python] 기본적인 탐색 알고리즘 2 - BFS

기본적인 탐색 알고리즘 관련 내용은 이전 포스팅 참고

[python] 기본적인 탐색 알고리즘 1 - DFS

 

이번 포스팅에선 너비우선탐색 Breath-First Search (BFS)에 대해 알아보는 시간을 갖겠습니다.

 

BFS 원리 설명

depth가 얕은 것부터 우선적으로 탐색하는 모양의 그림을 볼 수 있다

위 그래프와 리스트는 BFS의 전형적인 문제해결 방법을 나타냅니다.

 

DFS와 다른점이 있다면, 어떠한 노드를 탐색했을 때, 해당 노드의 자식 노드를 가장 우선적으로 탐색하는 방법이 아닌 오픈리스트 맨 마지막에 추가하여 가장 나중에 탐색하여 넓게 넓게 확인하며 다음 깊이로 넘어가는 탐색 방법을 채택하고 있습니다.

간단하게 유사코드로 확인해보죠.

# BFS 설명을 위한 유사코드

초기 상태 (최상단에 위치한 노드)를 open list로 넣고, closed list는 빈 리스트로 시작

while open list:
	
    - open list의 첫 요소(a)를 꺼내고, a를 closed list로 이동 (a 탐사 완료)
    - a가 목표 상태라면 해를 발견하였으므로 탐색 종료
    - a에 인접한 상태 중 아직 탐사하지 않은 상태(자식 노드)를 모두 open list의 첫 요소를 제외한 나머지 부분(tail)에 추가

결정적으로 BFS는 open list에 새로운 요소를 추가하는 방법이 DFS와 다르다는 점을 염두에 두면 됩니다.

 

BFS 파이썬 코드 구현

지난 DFS와 같은 예제를 통해  BFS 파이썬 코드를 구현해보겠습니다.

 

위 미로를 그래프로 그렸을 때의 모습

 

# 그래프의 노드를 dictionary 형태로 표현 
# 자세한 내용은 DFS 포스팅 참고
graph = {
    '0' : ['3'],
    '3' : ['4', '7'],
    '4' : ['6', '1'],
    '7' : ['9', '8'],
    '6' : ['2', '100'],
    '2': [],
    '100' : [],
    '1': [],
    '9': [],
    '8': ['10', '5'],
    '10': [],
    '5': []
}


# BFS

def bfs(graph, start_node):

    open, closed = [], []
    open.append(start_node)

    while open:
        node = open[0]
        del open[0]

        if node not in closed:
            closed.append(node)
            open.extend(graph[node])
        if node == '100':
            break
    return closed
    
    
bfs(graph, '0')

# ----- 출력물 ------
['0', '3', '4', '7', '6', '1', '9', '8', '2', '100']

위처럼 너비우선 탐색 (BFS)를 파이썬으로 구현해보았습니다.

 

BFS의 특징은 

- 초기 상태에 가까운 곳에 해가 있으면 해를 빠르게 발견할 수 있는 장점이 있고,

- 탐색 트리 구조가 가로로 넓은 경우(즉, 분기가 많은 경우) 오픈 리스트에 유지해야 할 노드의 수가 많다는 점이 특징입니다.

 

미로 탐색 예제를 통해 깊이우선 탐색과 너비우선 탐색에 대해 알아보았습니다.