DFS (깊이 우선 탐색) 이해하기

Minha Ahn·2024년 8월 21일

알고리즘 코테 파이썬

DFS란

Depth First Search라는 뜻으로, 깊이 우선 탐색이라고도 불린다.

그래프 자료에서 데이터를 탐색하는 알고리즘 중 하나이다.

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

이렇게 위에서부터 찾느냐, 옆에서부터 찾느냐에 따라 방식이 나뉘는데 위에서 아래로 찾는 방식을 바로 DFS라 부른다.

DFS의 기본 원칙

DFS에서 데이터를 찾을 때에는 아래의 기준대로 탐색한다.

앞으로 찾아 가야할 노드 => 계속 검색 진행

이미 방문한 노드 => 무시 or 따로 저장

파이썬으로 DFS 구현하기

파이썬에서 DFS를 구현하는 방법은 크게 2가지가 있다.

1) 스택/큐를 이용하는 방식
2) 재귀함수를 이용하는 방식

오늘은 이 두 가지 방식을 완벽하게 이해해보도록 하겠다.

참고 데이터

graph = dict()
 
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

1. 스택/큐를 이용하는 방식

스택/큐를 이용하는 방식도 리스트를 이용하는 방식과 collections 패키지의 deque를 이용하는 방식이 있다. 이 두 방식은 논리 구조가 동일하나, 성능면에서는 리스트보다는 deque가 훨씬 좋다는 점만 명심하면 될 것 같다.

(1) 리스트를 활용한 DFS 구현

def dfs(graph, start_node):
	
    # 2개의 리스트로 관리하기
    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

(2) deque를 활용한 DFS 구현

from collections import deque

def dfs(graph, start_node):
	
    # 2개의 리스트로 관리하기
    need_visited = deque()
    visited = []
    
    # 나머지 동일
    ...
            
    return visited

구조 이해하기

2. 재귀함수 이용하는 방식

def dfs_recursive(graph, start, visited = []):
	
    # 시작 노드를 방문 기록에 남기기
    visited.append(start)
    
    # 시작 노드와 인접한 모든 노드를 순회하며
    for node in graph[start]:
    
    	# 시작 노드와 인접한 노드에 아직 방문하지 않았다면,
    	if node not it visited:
        
        	# 그 노드를 시작 노드로 삼아 그 인접 노드 순회
        	dfs_recursive(graph, node, visited)
    
    return visited