[자료구조] 그래프 DFS/BFS Python pseudo코드로 이해하기

Understanding DFS/BFS Algorithm through python pseudo-code

 

비전공자로서 자료구조를 공부하다보면 실제 문제에 적용하기 힘든 경우가 많다.

특히 입문자로서 코딩테스트 빈출 유형인 DFS / BFS는 단순히 이론을 공부하거나 다른 사람들의 코드를 보는 것으로 실력을 쌓는 것은 꽤나 먼 일처럼 느껴진다.

필자의 경우 Graph문제에 대해 깊이 우선 탐색(DFS) / 너비 우선 탐색(BFS) pseudo-code를 이해하는 것이 효과적이었어서 정리할 겸 포스팅하게 되었다.

 

DFS

깊이 우선 탐색의 경우 두 가지 방법이 존재한다.

재귀적으로 문제를 해결하는 방식과, 반복 구조로 문제를 해결하는 방식이다.

재귀적으로 깊이 우선 탐색을 수행하는 방법

def recursive_dfs(vertex, visited=[]):
    visited.append(vertex) # 첫 Node(vertex)를 방문 처리
    for adj_v in graph[vertex]: # 현재 Node의 하위 노드들에 대해
    	if adj_v not in visited: # 방문 처리되지 않았다면
        	visited = recursive_dfs(adj_v, visited) # 하위 노드에 대해 방문 처리함을 반복한다.
    return visited

재귀적인 깊이 우선 탐색의 경우, 하나의 Node의 하위 Node에 대해 탐색 반복하는 방식으로 작동한다.

그래프의 하위 노드들에 대한 시행이 끝날 때까지 반복하고, 그렇지 않으면 다음 노드로 이동하므로 깊이 우선 탐색이라고 할 수 있다.

 

반복적으로 깊이 우선 탐색을 수행하는 방법

def iterative_dfs(start_vertex):
    visited = [start_vertex] # 시작 노드를 방문 처리
    stack = [start_vertex] # Stack을 쌓아나가며 탐색
    
    while stack: # Stack을 모두 탐색할 때까지
    	v = stack.pop() # Stack의 첫 노드
        
        if v not in visited: # 하위 노드를 반복하기 전에 첫 하위노드가 방문 처리되었는지 확인
            visited.append(v) # 방문 처리
            for adj_v in graph[v]: # 추후 탐색해야 할 Stack에 하위 노드들을 삽입
            	stack.append(adj_v)
    return visited

위 재귀적 깊이 우선 탐색에서 "하위 노드들에 대한 시행이 끝날 때까지" 반복한다고 하였는데, 이를 while로 구현한 것이다.

방문 처리되지 않은 Node에 대해 하위 항목들을 후입하여 하위 첫 항목만 반복하여 탐색한다.

한 방향의 하위 노드들을 모두 탐색하고 나면 Stack에 쌓인 다음 노드를 탐색하는 방식으로 작동한다.

특이점이라면 Stack을 활용한다는 것인데 후술할 너비 우선 탐색의 Queue를 이용하는 방식과 대비된다.

 

BFS

너비 우선 탐색의 경우 같은 depth를 가지는 Node들을 모두 탐색한 뒤에 하위 depth의 Node들을 탐색하는 방식이다.

위 DFS와 달리 재귀적인 구현이 불가능하며, Queue를 이용한다.

너비 우선 탐색 수행

def bfs(start_vertex):
    visited = [start_vertex]
    queue = [start_vertex]
    
    while queue: # queue를 모두 탐색할 때까지
        v = queue.pop() # queue 하나의 노드에 대해
        
        for adj_v in graph[v]: # 인접 하위 노드들 모두를 탐색
            if adj_v not in visited: # 만약 인접 하위 노드들 중 방문 처리되지 않은 것이 있다면
            	visited.append(adj_v) # 방문 처리와 동시에
                queue.append(adj_v) # queue에 등록
    return visited

반복 DFS 코드와 비교하였을 때, BFS 알고리즘은 while 시행과 동시에 for - if문으로 이어진다.

즉, 하위 첫 노드를 if-for문으로 골라내어 Stack에 쌓는 DFS와는 다르게 하위 인접 노드들을 모두 탐색하면서 방문 처리한다.

선입 선출 구조의 Queue를 사용하는 이유도 하위 노드를 탐색하고 나면 바로 같은 depth를 가지는 상위 노드로 돌아와야 하기 때문이다.