1. 너비 우선 탐색(BFS, Breadth-First Search)
1. 너비 우선 탐색이란
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
- 즉, 깊게(deep)탐색하기 전에 넓게(wide)탐색하는 것
- 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용
- 예) 지구상에 존재하는 모든 친구관계를 그래프로 포현한 후 '철수'와 '영희'사이에 존재하는 그래프를 찾는 경우
- 깊이 우선 탐색 : 모든 친구 관계를 다 살펴봐야할지도 모름
- 너비 우선 탐색 : 철수와 가까운 관계부터 탐색
- 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡함
2. 너비 우선 탐색의 특징
- 직관적이지 않은 면이 있다.
- BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
- BFS는 재귀적으로 동작하지 않는다.
- 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.
- 이를 검사하지 않은 경우 무한루프에 빠질 위험이 있음
- BFS는 방문한 노드들을 차례로 저장한 후 꺼낼수 있는 자료 구조인 큐(Quere)를 사용한다.
- 즉, 선입선출(FIFO)원칙으로 탐색
- 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작함
3. 너비 우선 탐색의 과정
- 깊이가 1인 노드를 방문하고 그 다음에는 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.
A -> B -> C -> D -> E -> F -> G -> H -> I -> J 순으로 탐색한다.
역시 그래프를 순차적으로 방문할 수 있어야 하고, 방문한 노드들은 다시 탐색할 일이 없도록 방문 처리해야 한다.
너비 우선 탐색 알고리즘을 코드로 나타내면 다음과 같다.
from collections import deque # deque 모듈을 가져옴
import maze_puzzle as mp # maze_puzzle 모듈을 mp로 가져옴
def run_bfs(maze_puzzle, current_point, visited_points):
queue = deque() # 빈 deque 생성
queue.append(current_point) # 시작 지점을 큐에 추가
while queue: # 큐가 비어있지 않은 동안 반복
current_point = queue.popleft() # 큐의 왼쪽에서 현재 지점을 추출하여 꺼냄
neighbors = maze_puzzle.get_neighbors(current_point) # 현재 지점의 이웃 지점들을 가져옴
for neighbor in neighbors: # 이웃 지점들에 대해 반복
if not is_in_visited_points(neighbor, visited_points): # 이웃 지점이 방문한 지점이 아니라면
neighbor.set_parent(current_point) # 이웃 지점의 부모를 현재 지점으로 설정
queue.append(neighbor) # 이웃 지점을 큐에 추가
visited_points.append(neighbor) # 이웃 지점을 방문한 지점 리스트에 추가
if maze_puzzle.get_current_point_value(neighbor) == '*': # 이웃 지점이 목적지인 경우
return neighbor # 목적지 반환
return "No Path to the goal found." # 목적지까지의 경로가 없는 경우 메시지 반환
def is_in_visited_points(current_point, visited_points):
for visited_point in visited_points: # 방문한 지점 리스트에 대해 반복
if current_point.x == visited_point.x and current_point.y == visited_point.y: # 현재 지점이 방문한 지점이면
return True # True 반환
return False # 아니면 False 반환
print("--Breath-first Search--")
maze_game_main = mp.MazePuzzle() # MazePuzzle 클래스의 인스턴스 생성
starting_point = mp.Point(2,2) # 시작 지점 설정
outcome = run_bfs(maze_game_main, starting_point, []) # BFS 알고리즘으로 미로 탐색
bfs_path = mp.get_path(outcome) # 경로 추출
print("Path Length:", len(bfs_path)) # 경로 길이 출력
maze_game_main.overlay_points_on_map(bfs_path) # 미로 지도에 경로 표시
print("Path Cost : ", mp.get_path_cost(outcome)) # 경로 비용 출력
for point in bfs_path: # 경로 상의 각 지점에 대해
print("Point:", point.x, ',', point.y) # 해당 지점의 좌표 출력실행 결과
--Breath-first Search--
Path Length: 8
@0000
@###0
@#0#0
@#@00
@@@00
Path Cost : 16
Point: 0 , 0
Point: 1 , 0
Point: 2 , 0
Point: 3 , 0
Point: 4 , 0
Point: 4 , 1
Point: 4 , 2
Point: 3 , 2
Robotics