깊이 우선 탐색
깊이 우선 탐색(Depth First Search)이란 그래프 탐색 방법 중 하나로, 최근에 방문한 정점을 선택한 뒤, 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 주로 깊이 우선 탐색과 같이 언급되는 알고리즘이다.
단순 검색 속도는 BFS보다 느리기 때문에 검색이 아닌 순회할 때 많이 사용한다. 즉, 방문할 수 있는 모든 정점을 확인해야 할 때 깊이 우선 탐색을 사용한다. 또한 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법인 백트래킹, 그리고 자동 미로 생성에서 많이 사용한다.
참고로 깊이 우선 탐색으로 찾은 결과는 최단 경로가 된다는 보장은 없다. 또한 해가 없을 경우를 고려하여 탐색할 깊이를 미리 지정할 필요가 있다.
동작 방식
임의 정점의 인접한 정점을 모두 기억해야 하는 BFS와 달리 깊이 우선 탐색은 현재 경로 상의 정점들만 기억하면 되기 때문에 재귀호출이나 스택 배열을 사용하여 구현한다.
아래 그림은 깊이 우선 탐색 과정을 나타낸 것이다.
- 시작 점점인 a를 방문한다.
- a의 방문 여부를 갱신한다.
- a와 인접한 정점을 확인한다.
- 인접한 정점이 없으면 종료한다.
- a와 인접한 정점 b를 방문한 경우, b를 시작 정점으로 하고 깊이 우선 탐색을 수행한다.
- a와 인접했으나 방문하지 않은 정점을 방문하기 전에 b의 인접한 정점을 전부 방문해야 한다.
- b의 인접한 정점을 전부 방문했으면 a와 인접했으나 방문하지 않은 정점을 찾는다.
- 아직 방문하지 않은 정점이 없으면 종료한다.
- 있으면 해당 정점을 시작 정점으로 깊이 우선 탐색을 수행한다.
구현 코드
깊이 우선 탐색을 Python으로 구현한 코드는 다음과 같다.
- 재귀 함수 방식
def dfs_recursive(graph, start, visited = []):
visited.append(start)
for node in graph[start]:
if node not in visited:
dfs_recursive(graph, node, visited)
return visited
- 스택 방식
from collections import deque
def dfs(graph, start_node):
visited = []
need_visited = deque()
##시작 노드
need_visited.append(start_node)
## 방문할 정점이 저장된 큐가 빌 때까지 반복
while need_visited:
## 시작 노드를 지정하고
node = need_visited.pop()
##만약 방문한 리스트에 없다면
if node not in visited:
## 방문 리스트에 노드를 추가
visited.append(node)
## 인접 노드들을 방문 예정 리스트에 추가
need_visited.extend(graph[node])
return visited
참고 문서
728x90