DFS/BFS

DFS/BFS를 이용하여 푸는 문제는 코딩 테스트에서 흔히 나오는 유형 중 하나입니다.

알고리즘 및 자료구조에서 탐색 (search) 란, 많은 양의 데이터 중에서 원하는 특정 데이터를 찾는 과정을 의미합니다.

DFS는 depth-first search, 즉 깊이 우선 탐색이라고 불리며, BFS는 breadth-first search, 즉 너비 우선 탐색이라고 불립니다.

두 방법 모두 이름에서 알 수 있듯 탐색 (search)를 수행하는 알고리즘입니다.

이를 이해하기 위해서는 먼저 stack과 queue, 그리고 재귀 함수에 대한 이해가 선행되어야 합니다. 이 글에서는 해당 내용들을 전부 알고 있다고 전제하겠습니다.

 

DFS와 BFS는 모두 그래프 자료구조를 탐색할 떄 사용하는 알고리즘입니다. 그래프에 대해 간단히 다루는 것으로 시작하겠습니다.

그래프는 정점(vertex, node라고도 함)과 간선 (edge)로 이루어진 자료구조입니다.

그래프 자료구조에는 1개 이상의 정점이 존재합니다. 이 정점들을 잇는 간선들은 0개 이상 존재합니다.

즉, 정점 A, B, C가 있고, A-B를 잇는 간선, B-C를 잇는 간선이 존재할 수 있습니다.

각 정점과 간선은 값을 가지는 경우도 있고, 그렇지 않은 경우도 있습니다. 이는 자료구조가 나타내는 실제 모델에 따라 달라집니다.

 

이해를 돕기 위해 비유를 하자면, 정점을 도시에 비유할 수 있고, 도로를 간선에 비유할 수 있습니다.

아주 간단한 형태의 그래프 자료구조

이 경우, 정점은 특정한 값을 가지지 않지만, 간선은 실제 도로의 거리의 값을 가질 수 있습니다.

또, 다음과 같은 그래프 역시 존재할 수 있습니다.

실제 도시-도로를 노드-간선의 형태로 나타낸 그래프

위 그래프에서는 간선은 단순히 정점 간의 연결 여부를 나타내게 됩니다.

 

그래프는 array 또는 linked list를 사용하여 나타내게 됩니다.

Array를 이용하는 경우, 총 N개의 정점이 있을 때, N x N 크기의 2차원 array를 만들고, array 내에는 간선의 유무 및 가중치를 적게 됩니다.

예를 들어 N = 8일 때, 정점 3과 7이 연결되어 있고, 별도의 가중치가 존재하지 않는다면, array[3][7]과 array[7][3]에 각각 1을 기록합니다. 정점 2와 8은 연결되어 있지 않은 경우, array[2][8]과 array[8][2]에 각각 0을 기록합니다.

 

그래프의 예시

Linked list를 이용하는 경우, 모든 노드에 연결된 노드 정보를 차례로 연결하여 저장합니다.

1번 노드는 2번 노드, 3번 노드 에 연결되어 있고, 2번 노드는 번 노드, 6번 노드에 연결되어 있고, 3번 노드는 1번 노드, 4번 노드, 5번 노드, 7번 노드에 연결되어 있고...

이를 STL로 제공되는 linked list를 이용하여 나타내면 됩니다.

 

Array를 이용하는 방식은 2차원 array를 미리 선언하고, 중복으로 저장되는 값들 및 불필요한 값들의 공간까지 차지하기 때문에, 메모리를 조금 더 많이 사용합니다. 위의 예시에서 보았듯, 정점 3과 7에 대한 연결 정보를 중복하여 저장하였고, array[3][3]은 자신에 대한 연결 여부를 나타내므로 불필요한 영역입니다.

반면 Linked list를 이용하는 방법은 상대적으로 메모리를 덜 차지한다는 장점이 있습니다.

또, Array 방식은 원하는 두 정점의 연결 여부를 바로 접근할 수 있으므로, 접근 속도가 빠릅니다.

Linked list 방식은 최악의 경우 list의 끝까지 확인해 봐야 하므로 상대적으로 접근 속도가 느립니다. 위 그래프에서, 3번 노드와 6번 노드가 연결되어 있는지 확인하고 싶다면, list의 끝까지 전부 확인해본 후에야 3번과 6번은 연결되어 있지 않다는 것을 알 수 있습니다.

 

DFS

DFS (depth-first search, 깊이 우선 탐색)는 그래프 자료 구조에서 깊은 부분을 우선적으로 하여 탐색하는 알고리즘입니다. 스택 (혹은 재귀 함수) 자료 구조를 사용하며, 동작 구조는 다음과 같습니다.

1. 탐색 시작 노드를 스택에 삽입하고, 해당 노드를 방문 처리 합니다.
2. 스택의 최상단 노드를 확인합니다. 이 노드에 인접한 노드들 중 방문하지 않은 노드가 있으면, 스택에 넣고 방문 처리를 합니다. 방문하지 않은 인접 노드가 없다면, 스택에서 최상단 노드를 꺼냅니다.
3. 2번을 더 이상 수행할 수 없을 때까지 반복합니다.

DFS를 수행하는 과정입니다.

위 움짤에서 빗금 친 노드는 방문했음을 나타냅니다.

결과적으로, 탐색 순서는 다음과 같게 됩니다:

1 > 2 > 6 > 7 > 3 > 4 > 5 > 8

 

BFS

BFS (breadth-first search, 너비 우선 탐색)는 그래프 자료 구조에서 너비 우선, 즉 가까운 노드를 우선하여 탐색하는 알고리즘입니다. DFS와는 반대인 셈인데, 이를 나타내듯 큐 자료구조를 이용합니다.

인접한 노드를 반복적으로 큐에 넣게 되어, 먼저 들어온 것이 먼저 나가며 가까운 노드부터 탐색을 진행하게 됩니다. 동작 구조는 다음과 같습니다.

1. 탐색 시작 노드를 큐에 삽입하고, 해당 노드를 방문 처리 합니다.
2. 큐에서 노드를 꺼내고, 해당 노드의 인접한 노드들 중에서 방문하지 않은 노드들을 모두 큐에 넣으며 동시에 방문 처리 합니다.
3. 2번을 더 이상 수행할 수 없을 때까지 반복합니다.

같은 그래프를 이용하여 예를 들어 보겠습니다.

BFS를 수행하는 과정입니다.

결과적으로, 탐색 순서는 다음과 같게 됩니다:

1 > 2 > 3 > 8 > 7 > 4 > 5 > 6

 

*본 글은 "나동빈, 이것이 취업을 위한 코딩 테스트다 with 파이썬" (한빛미디어, 2020)" 를 참고하여 작성하였습니다.