그래프 탐색이란
- 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
1. 깊이 우선 탐색
1. 깊이 우선 탐색이란
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
- 트리를 이동하거나 트리의 노드와 경로를 생성하는 알고리즘
- 특정 노드에서 시작하여, 첫 번째 자식 노드에 연결된 경로를 검색하고, 또다시 그 노드의 첫 번째 자식 노드의 경로를 검색
- 첫 번째 자식 노드로부터 가장 먼 리프노드에 도달할 때까지 반복해서 검색을 수행
- 리프 노드에 도달한 다음에는, 이미 방문한 리프 노드의 부모 노드를 역추적해서 방분하지 않은 다른 자식 노드에 대해 같은 방식으로 다시 검색
- 미로를 탐색할때 한 방향으로 갈 수 있을때까지 게속 가다가 더 이상 갈수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사
- 즉, 넓게(wide)탐색하기 전에 깊게(deep)탐색하는 것이다.
- 사용하는 경우: 모든 노드를 방문하고자 하는 경우에는 이 방법을 선택
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
- 단순 검색 속도 자체는 너비 우선 탐색에 비해서 느리다.
2. 깊이 우선 탐색(DFS)의 특징
- 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
- 전위 순휘(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
- 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다.
- 이를 검사하지 않은 경우 무한 루프에 빠질 위험이 있다.
3. 깊이 우선 탐색의 과정
위와 같은 그래프에서 A를 시작 정점으로 깊이 우선 탐색을 한다면 순서는 다음과 같다.
A -> B -> D -> H -> I -> E -> J -> C -> F -> G 순으로 탐색한다. 이 탐색 과정을 구현하기 위해서는 먼저 그래프를 순차적으로 방문할수 있어야 하고, 방문한 노드들은 다시 탐색할 일이 없도록 방문 처리되어야 한다.
2. 미로 찾기
아래와 같은 미로가 주어질 때, 주어진 미로가 탈출 가능한 미로라면 True, 탈출 불가능한 미로라면 False를 반환
해당 문제를 풀기 위해 갈수 있는 길은 0, 갈 수 없는 길은 1로 표시하고 스택을 선언
처음 시작점인(0,0)검사 -> 도착 지점이 아니기 때문에 (0,0)에서 갈 수 있는 모든 경우의 수를 스택에 추가
(0,1)지점 검사 -> 도착 지점이 아니기 때문에 (0,1)에서 갈 수 있는 모든 경우의 수를 스택에 추가
(0,2) 지점 검사 -> 도착 지점이 아니기 때문에 (0,2)에서 갈 수 있는 모든 경우의 수를 스택에 추가 ... 이 과정 반복
(2,3) 지점에서 더 이상 갈 수 있는 곳이 없음 -> 아무것도 추가 x
(1,1) 지점 검사 -> 도착 지점이 아니기 때문에 (1,1)에서 갈 수 잇는 모든 경우의 수를 스택에 추가
...이 과정을 정답을 찾을때까지 반복(5,5)지점에서는 도착 지점에 도착했기 때문에 True반환
깊이 우선 탐색 로직을 코드로 짜면 다음과 같다.
import maze_puzzle as mp
def run_dfs(maze_game, current_point):
visited_points = []
stack = [current_point]
while stack:
next_point = stack.pop()
if not is_in_visited_points(next_point, visited_points):
visited_points.append(next_point)
if maze_game.get_current_point_value(next_point) == '*':
return next_point
else:
neighbors = maze_game.get_neighbors(next_point)
for neighbor in neighbors:
neighbor.set_parent(next_point)
stack.append(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
return False
print("---Depth-first-Search")
maze_game_main = mp.MazePuzzle()
starting_point = mp.Point(2,2)
outcome = run_dfs(maze_game_main, starting_point)
dfs_path = mp.get_path(outcome)
print("Path Legth : ", len(dfs_path))
maze_game_main.overlay_points_on_map(dfs_path)
print("Path Cost:", mp.get_path_cost(outcome))
for point in dfs_path:
print("Point: ", point.x, ',', point.y)실행 결과
Path Legth : 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