[알고리즘] BFS/DFS 알고리즘 (그래프 탐색)

그래프 탐색(Graph Search)

그래프 탐색이란 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것을 말한다. 단순히 그래프의 노드를 탐색하는 것으로 문제를 해결한다. 그래프 탐색에는 BFS/DFS가 있다. 

✔ BFS(Breadth First Search) 정의

너비 우선 탐색이라는 뜻이고, 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. 아래의 그림을 보면서 쉽게 이해해보자.

위의 그림과 같이 6개의 노드와 5개의 간선(노드의 개수-1)이 있다. 노드 1번부터 시작해서 2번을 탐색하고 다음으로 4번 노드를 탐색하는 게 아닌 3번 먼저 탐색하는 것이다. 3번 옆에 아무것도 없으므로 다시 2번 노드로 돌아와서  2번 노드의 하위 노드 중 하나인 4번을 탐색한다. 4번을 끝냈으면 다음 5번, 마지막으로 6번 노드를 탐색을 끝으로 트리를 모두 탐색한 것을 보여준다. 

우측 그림의 NxN 그리드일 경우도 보자. 4x4 그리드일 경우도 마찬가지로 1번부터 시작해서 오른쪽으로 탐색을 한다. 4번 칸의 탐색이 끝났으면 5번부터 다시 오른쪽으로 탐색한다. 위 과정을 계속 반복하면 16번까지 탐색을 끝으로 모든 칸의 탐색이 끝이 난다.

 

Queue(큐)를 이용

BFS는 큐를 이용해서 문제를 푼다. 간단히 큐에 대해 알아보자.

 

Queue(큐) 자료구조란?

FIFO(First In First Out) 구조이고, 먼저 들어온 데이터가 큐에 먼저 들어가고, 큐에서 나올 때도 먼저 들어온 데이터가 빠지는 것을 말한다. 아래 그림을 보면, 큐에 0번 노드가 먼저 들어와 있으니 큐에서 나갈 때도 0번이 먼저 나가야 하는 것이다.

다음 예시를 보고 큐를 이용해 BFS의 동작 방식을 살펴보자.

위와 같은 그래프와 큐가 주어졌다고 하자. 인접한 노드가 여러 개 있을 때, 숫자가 작은 노드부터 먼저 큐에 삽입한다고 가정한다. (큐에서 꺼내 처리하는 노드는 하늘색으로, 방문 처리된 노드는 회색으로 표시) 

 

① 시작 노드를 0으로 정한다. 0을 큐에 삽입하고 방문 처리한다.

② 큐에서 0을 꺼내고 0과 인접한 1을 큐에 삽입한다. 큐에 삽입된 1은 방문 처리한다.

③ 1을 큐에서 꺼내고 1과 인접한 2, 3을 큐에 모두 삽입한다. 2와 3은 방문 처리한다.

④ 2를 큐에서 꺼내고, 2와 인접한 4번 노드를 큐에 삽입하고 방문 처리한다.

⑤ 3을 큐에서 꺼내고, 3과 인접한 5번 노드를 큐에 삽입하고 방문 처리한다.

이런식으로 계속 반복하면 출력 결과는 ⓿❶❷❸❹❺❻❼❽

인접 노드를 모두 큐에 넣고 먼저 들어간 것부터 꺼낸다. 꺼냈으면 꺼낸 노드와 인접한 노드가 있으면 모두 큐에 넣고 반복한다. 

---

✔ DFS(Depth First Search) 정의

깊이 우선 탐색이라는 뜻이고, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 아래의 그림을 보면서 쉽게 이해해보자. 

노드 1번부터 시작해서 2번을 탐색하고 다음으로 2번 하위 노드 중 3번과 4번 노드를 탐색한다. 3번 하위노드는 없으므로, 2번 하위 노드인 4번 노드를 탐색한다. 4번 하위노드도 없으므로, 1번노드로 돌아와 탐색하지 않은 5번 노드를 마저 탐색한다. 5번 노드를 탐색하고, 마지막으로 하위노드인 6번 노드를 탐색을 끝으로 트리를 모두 탐색한 것을 보여준다. 

우측 그림의 NxN 그리드일 경우도 보자. 4x4 그리드일 경우도 마찬가지로 1번부터 시작해서 아래쪽으로 탐색을 한다. BFS 때와는 오른쪽으로 탐색을 했지만 DFS는 아래쪽으로 탐색을 한다. 13번 칸의 탐색이 끝났으면 2번부터 다시 아래쪽으로 탐색한다. 위 과정을 계속 반복하면 16번까지 탐색을 끝으로 모든 칸의 탐색이 끝이 난다. 

Stack(스택)을 이용

DFS는 큐를 이용해서 문제를 푼다. 간단히 스택에 대해 알아보자.

 

Stack(스택) 자료구조란?

FILO(First In Last Out) 구조이고, 먼저 들어온 데이터가 스택에 먼저 들어가고, 스택에서 나올 때는 나중에 들어온 데이터가 먼저 빠지는 것을 말한다. 아래 그림을 보면, 스택에 0번 노드가 먼저 들어와 있으나 스택에서 나갈 때는 1번이 먼저 나가야 하는 것이다. 스택의 출입구가 동일하므로, 한쪽은 막혀있다고 생각하면 된다.

다음 예시를 보고 스택 이용해 BFS의 동작 방식을 살펴보자.

위와 같은 그래프와 스택이 주어졌다고 하자. 인접한 노드가 여러 개 있을 때, 숫자가 작은 노드부터 먼저 스택에 삽입한다고 가정한다. (스택에서 꺼내 처리하는 노드는 하늘색으로, 방문 처리된 노드는 회색으로 표시) 

 

① 시작 노드를 0으로 정한다. 0을 스에 삽입하고 방문 처리한다.

② 현재 스택의 최상단 노드인 0에 방문하지 않은 인접 노드인 1이 있으므로 1을 스택에 삽입한다. 스택에 삽입된 1은 방문 처리한다.

③ 현재 스택의 최상단 노드인 1에는 방문하지 않은 인접 노드 2, 3이 있다. 이 중 가장 작은 노드인 2를 스택에 넣고 방문 처리한다.

④ 현재 스택의 최상단 노드인 2에는 방문하지 않은 3과 4가 있다. 이 중 가장 작은 노드인 3을 스택에 넣고 방문 처리한다.

⑤ 현재 스택의 최상단 노드인 3에는 방문하지 않은 4와 5가 있다. 그 중 가장 작은 노드인 4를 스택에 넣고 방문 처리한다.

⑥ 현재 스택의 최상단 노드인 4에는 방문하지 않은 인접 노드가 없다. 따라서 스택에서 4번 노드를 꺼낸다.

⑦ 현재 스택의 최상단 노드인 3에는 방문하지 않은 인접 노드 5가 있다. 5를 스택에 넣고 방문 처리한다.

이런식으로 계속 반복하면 출력 결과는 ❹❽❻❼❺❸❷❶⓿. 

BFS에서는 인접 노드를 모두 큐에 넣었지만, DFS에서는 인접 노드 중 가장 작은 노드 하나만 넣는다. 그리고 빼내면서 인접 노드를 탐색하는 것이 아니라, 스택에 들어있는 최상단 노드의 인접 노드가 더 이상 없을 때 빼낸다. 

---

문제 풀이

 

1260번: DFS와 BFS