[3주차] 그래프 탐색 - 깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS)

사진: Unsplash 의 Scar Tissue

 

지난 포스팅에서 비선형 자료구조인 '그래프'와 그래프에 속하지만 사이클이 없고 방향이 위에서 아래로 존재하는 자료구조인 '트리'의 기본 골자를 알아봤다.

이번 포스팅에서는 그 그래프를 탐색하는, 맹목적 탐색 방법의 대표적인 두 가지 방법에 대해 알아보려고 한다.

나는 solved.ac의 내가 푼 문제 편향을 보았을 때, 이 그래프를 다루는 문제를 무척이나 많이 풀었다.

그만큼 그래프 탐색은 한 번 알아두면 정말 깊게 파내려갈 수 있는 주제라고 생각한다. (개인적으로요)

 

---

1. 깊이 우선 탐색 (DFS; Depth First Search)

사진 출처 : 위키백과 - 깊이 우선 탐색

 

깊이 우선 탐색(이하 DFS 라고 한다)은 그래프 순회 방식의 일종으로, 이름에서 파악이 가능하다시피 특정 노드에서 그 노드가 가지는 한 자식들의 끝까지 최대한 깊숙이 들어가서 탐색한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다.

 

조금 더 쉽게 말해서, 한 노드에서 뻗은 가지 중에서 한 갈래의 길을 파내려가 리프 노드(leaf node)에 도달할 때까지 탐색 후 다시 돌아와 다른 갈래의 길을 탐색하는 방법이다.

 

방향이 있는 유향 그래프에서 사이클이 존재하는지 파악하는 것이 가능하다. 어떤 한 노드에서 간선을 따라 방문하다 보면 자기 자신으로 돌아올 수 있는 경로의 여부를 확인할 수 있기 때문이다.

 

※ 구현

• 스택(stack) 자료구조
• 재귀 (Recursive)

 

※ 장점

• 현 경로상의 노드들만 기억하면 되기에 저장공간의 수요 비교적 적음
• 목표 노드가 깊은 단계(level)에 있을 경우, 해를 빠르게 구할 수 있다.

※ 단점

• 해가 없는 경로에 깊이 빠질 수 있다. 따라서 깊이 제한이 유용하게 작용할 수 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다. 왜냐하면 목표 노드에 이르는 경우의 수가 다수일 경우 DFS의 경우 목표 노드에 한 번 다다르면 탐색이 끝나기 때문이다.

※ 깊이 제한과 백트래킹

 

단점에서 이야기한 '해가 없는 경로에 깊이 빠질 수 있다.' 의 보완책으로 깊이 제한(depth bound)을 사용한다.

깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 최근의 부모 노드로 되돌아온다.

그리고 이 되돌아오는 과정을 백트래킹(backtracking)이라고 한다.

 

※ Python3 예시 코드

def dfs(graph:Dict, start:int): # Dict 자료형 형태로 준다. key는 노드, value는 인접노드를 가리킨다.
    visited = {i:False for i in graph.keys()} # 방문 배열. visited[node] = True이면 node는 방문이 끝난 상태이다.
    def search(current:int): # 재귀함수 정의
        visited[current] = True # current 방문
        for nxt in graph[current]: # current의 인접 노드를 확인한다. 이 노드를 nxt라고 하자.
            if not visited[nxt]: # 만일 nxt에 방문하지 않았다면
                search(nxt) #nxt 방문
    search(start)

 

 

2. 너비 우선 탐색 (BFS; Breadth First Search)

 

사진 출처 : 위키독스, 위키백과 '너비 우선 탐색'

 

 

너비 우선 탐색(이하 BFS라고 한다)은 시작 노드를 방문한 후 시작 노드에 인접한 모든 정점들을 우선 방문하는 방법이다.

더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 BFS를 적용한다.

 

쉽게 말해 그래프의 너비, 그리고 특정 한 노드와 같은 레벨의 노드를 우선적으로 탐색하는 방법이다.

 

DFS와 대비되는 특징으로, 무한한 길이의 경로에서 영원히 탐색이 종료되지 않을 가능성이 높은 DFS와 달리 BFS는 모든 경로를 동시에 탐색하기에 탐색이 가능하다.

 

추가적으로 BFS의 강력한 특징으로 '가중치가 없는 그래프'에서 시작 노드에서 끝 노드까지의 최단 경로를 알아낼 수 있다. 

(가중치가 추가된 그래프의 경우 '다익스트라 알고리즘'을 활용한다)

 

※ 구현

• 큐 (Queue
  
  

※ 장점

• 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장한다.

※ 단점

• 경로가 매우 길 경우에는 한 번에 탐색해야할 탐색 가지가 급격히 증가하므로 보다 많은 물리적 기억 공간을 요구한다.
• 해가 존재하지 않는 유한 그래프의 경우 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프의 경우 결코 해를 찾아낼 수 없다.

※ python3 예시 코드

def bfs(graph:Dict, start:int): # Dict 자료형 형태로 준다. key는 노드, value는 인접노드를 가리킨다.
    visited = {i:False for i in graph.keys()} # 방문 배열. visited[node] = True이면 node는 방문이 끝난 상태이다.
    queue = [start]
    visited[start] = True
    while queue: # 큐가 빌 때까지 반복
        current = queue.pop(0) #queue에서 노드를 하나 빼 온다. 이 노드를 current라고 하자.
        for nxt in graph[current]: # current의 인접 노드들을 확인한다. 이 각각의 노드를 nxt라고 하자.
            if not visited[nxt]: # 만일 nxt에 방문하지 않았다면
                #nxt 방문
                queue.append(nxt)
                visited[nxt] = True

 

출처

위키백과 - 깊이 우선 탐색 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

위키백과 - 너비 우선 탐색 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

나무위키 - 깊이 우선 탐색: https://namu.wiki/w/%EA%B9%8A%EC%9D%B4%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89

나무위키 - 너비 우선 탐색 : https://namu.wiki/w/%EB%84%88%EB%B9%84%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89