DFS란
말 그대로 깊은 부분을 우선적으로 탐색하는 기법이다.
이 알고리즘의 핵심은 스택(stack) 자료구조를 사용하는 것이다.
스택 자료구조는 FILO (First-In-Last-Out) 방식을 따른다. 즉 스택에 데이터를 집어넣을 때 순서와
스택에서 데이터를 꺼낼 때 순서가 역방향이라는 것이다.
DFS는 가능한 모든 경로(후보)를 탐색한다. 따라서, 불필요할 것 같은 경로를 사전에 차단하거나
하는 등의 행동이 없으므로 경우의 수를 줄이지 못한다. 따라서 N! 가지 경우의 수를 가진 문제는
DFS로 처리가 불가능할 것이다. DFS 알고리즘 구체적인 동작 과정은 아래과 같다.
- 탐색 시작 노드를 스택에 삽입하고 "방문처리"를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리를 한다.
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. - 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.
여기서 “방문처리” 란 탐색한 노드를 재방문하지 않도록 구분하는 것이다.
즉, 스택에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크하는 것이다.
물론 스택을 사용하지 않아도 구현은 가능하다.
파이썬에서 DFS를 구현할 때는 "스택/큐"를 활용할 수도 있고, "재귀함수"를 통해 구현할 수도 있다.
(1) 리스트를 활용한 DFS 구현
def dfs(graph, start_node):
# 기본은 항상 두개의 리스트를 별도로 관리해 주는 것
need_visited, visited = list(), list()
# 시작 노드를 시정하기
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위 코드는 need_visited 에서 추가된 Node들 중에서 가장 끝에 있는 것을 뽑아서 검색하는 방식이다.
이 부분이 스택을 활용한 방식인 것이다. 다만, list에서 pop을 활용하면 성능면에서 떨어지는 단점이 있다.
(1) deque를 활용한 DFS 구현
from collections import deque
def dfs2(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성능 면에서 list( ) 형태보다 deque 형태가 훨씬 좋다.
(1) 재귀함수를 활용한 DFS 구현
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 visitedvisited 자료형을 기본 함수 인자로 포함시키고,
방문한 리스트들을 재귀함수를 통해서 계속 visited에 담는 방식이다.
보통 DFS 를 구현할 때 재귀함수를 많이 활용한다.
