[알고리즘] DFS(Depth-First Search) 탐색 알고리즘이란?

 

 

 

 

 

그래프란 노드(Node)가 있고 노드를 연결한 간선(Edge)이 있는 자료구조이다. 그래프를 완전탐색하는 기본적인 알고리즘은 DFS와 BFS이다.

 

탐색을 하려면 우선 자료구조가 정의되어야 한다.

 

그래프(Graph)는 두 가지 방식으로 표현된다.

 

1. 인접행렬( 2차원 배열 )

2. 인접리스트 ( 리스트 )

 

행렬은 '인덱스'가 있다. 인덱스는 랜덤엑세스를 가능하게 하여, 특정노드에 접근하는 속도가 빠르다. 하지만 배열구조로 쓰레기값이 들어있는 공간도 유지를 해야하기에 메모리낭비가 심하다.

 

인접리스트방식은 리스트 자료구조를 이용한다. '연결' 방식의 자료구조인 만큼, 특정 노드를 시작으로 인접노드를 순회하는 경우 유리하다. '인덱스'가 아닌 '주소'로 인접노드에 접근하니 메모리 낭비도 적다. 그러나 랜덤엑세스가 아닌 참조를 통한 접근을 하여 탐색속도가 느리다. 

 

 

DFS(Depth-First Search) : 깊이우선탐색

 

DFS 알고리즘은 스택(Stack)으로 구현된다. 

 

 

보통 메소드의 경우, 호출되면 Stack영역에 프레임이 쌓인다. 고로, DFS 알고리즘은 재귀호출(Recursice Call)로 구현가능하다. 원리는 간단하다. 

 

 

 

 

 

 

Graph 자료구조를 참조하여, 인접노드를 방문하면서 Stack에 쌓아간다(push). 그리고 인접노드가 없는 노드(6)에 도달하면 해당 노드를 제거(pop)하고 7의 인접노드를 탐색한다. 

 

LiFO(Last In First Out)인 스택은 이전 방문한 노드정보를 기억하고 있기에, 깊이를 '우선' 탐색할 수 있게 된다. 큐(Queue)와 같은, FIFO(First in First Out) 구조는 이전 방문한 노드를 기억하지 못해 깊이를 우선 탐색할 수 없다. 

 

 

 

 

이때 방문이력은 배열을 하나 생성하여 관리한다. 이와같이, PUSH와 POP을 반복하여 인접노드를 탐색하면 그래프의 모든 노드의 탐색이 가능해진다. 

 

 

코드구현

재귀호출로 Stack영역 메모리를 활용하기에 따로 Stack자료구조를 만들 필요는 없다. 

 

 

# DFS 함수
def dfs(graph,v,visited):  
    visited[v] = True  #방문처리
    print(v,end=' ') #방문노드 출력
    
    for i in graph[v]: # 인접노드 순회
        if not visited[i]: # 방문이력 있는지 체크
            dfs(graph,i,visited) # 재귀호출
#Graph 자료구조        
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]    
]

#방문이력관리 배열
visited = [False]*9

#DFS 함수 호출
dfs(graph,1,visited)

 

 

 

---

 

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서