[알고리즘] DFS

민지의 회고록·2023년 1월 31일

1. DFS 개념

깊이우선탐색(Depth-First Search, DFS)
다음 브랜치로 넘어가기 전에 해당 브랜치를 완벽히 탐색하는 방법
한 방향으로 끝까지 탐색 후 더이상 갈 곳 이 없을 경우 다음 길로 이동하여 탐색
- 모든 노드를 탐색 할때 도움이 됨
- 단순 탐색에 있어 bfs 보다 느리며 좀 더 간단함

1) DFS 특징

자신을 호출하는 재귀 형태를 띔
전위 순회를 포함하는 트리 순회는 dfs 의 한 종류
방문 처리를 하지 않을경우 무한 루프에 빠질 수 있음

2. DFS 동작 과정

1) 시작 정점 방문

2) 시작 정점에서 한 방향으로 방문할 수 있는 depth 까지 방문

3) 더 이상 해당 방향으로 방문할 노드가 없다면 이전 노드로 돌아가 다른 방향으로 이동

3. DFS 파이썬 구현

1. deque 사용

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

2. 재귀 사용

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